An inequality as a functional equation (IMO 1977)

Claim. $P(n)$: for every $k\ge n$, $f(k)\ge n$.

*Base.* $P(1)$: all values of $f$ are at least $1$.

*Step.* Assume $P(n)$. Let $k\ge n+1$. Then $k-1\ge n$, so $f(k-1)\ge n$ by $P(n)$. Applying $P(n)$ again to the argument $f(k-1)\ge n$: $f(f(k-1))\ge n$. Therefore
$$f(k)>f(f(k-1))\ge n,$$
so $f(k)\ge n+1$. This proves $P(n+1)$.

Consequence 1. Taking $k=n$ in $P(n)$: $f(n)\ge n$ for all $n$.

Consequence 2: $f$ is strictly increasing. Apply Consequence 1 to $m=f(n)$: $f(f(n))\ge f(n)$. Hence $f(n+1)>f(f(n))\ge f(n)$.

Conclusion. Suppose $f(n)\ge n+1$ for some $n$. Since $f$ is increasing, $f(f(n))\ge f(n+1)$, contradicting $f(n+1)>f(f(n))$. So $f(n)\le n$. Together with $f(n)\ge n$: $f(n)=n$.

Verification. $f(n)=n$: $n+1>n$ ✓.

Lesson. For $f:\mathbb{N}\to\mathbb{N}$ with an inequality, prove a *lower bound by induction* (here "$f(k)\ge n$ for $k\ge n$"), then show monotonicity, which lets you "cancel" $f$ from both sides of an inequality.