Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

It is sufficient to show that the difference $\Delta(n) = f(n) - f(n-1)$ is 0 or 1 for all integer numbers $n \ge 2$, and $f$ is unbounded.

Clearly, $\Delta(n) = 0$, $2 \le n \le k+1$, provides the basis for an inductive proof. If $n > k+1$, apply the recurrence. By the induction hypothesis, $\Delta(n-1)$ is 0 or 1 and

$1 \le f(n-1) \le n-1$. Notice that $\Delta(n) = \Delta(n-f(n-1))$ if $\Delta(n-1) = 0$ and $\Delta(n) = \Delta(f(n-1))$ if $\Delta(n-1) = 1$ to conclude that $\Delta(n)$ is indeed 0 or 1.
To show that $f$ is unbounded, suppose, if possible, that $f$ achieves its maximum value $N$ for the first time at $m$ to deduce recursively that $N = f(m+n) = f(N) + f(m-N+n)$ for all positive integers $n$; that is, $f(m-N+n) = N-f(N)$, for all positive integers $n$. Setting $n \ge N$ yields a contradiction: $N = N-f(N)$. The conclusion follows.