Problem 1623

Lemma 1. For every natural number $x$, $\{f^n(x)\}$ is unbounded.
Proof. For every natural number $y$,
$$f^{f(y)}(x) \ge y + f(x) - 1,$$
So, send $y$ to the infinity, we are done.

Lemma 2. All the terms of the sequence $(f^n(x))$ are distinct.
Proof. If $i < j$ and $f^i(x) = f^j(x)$ then this sequence becomes periodic which contradicts the first lemma.

Back to our problem, by the first lemma $f(1) \ge 2$, set $y = 1, k = f(1)$, then
$$1 \ge 1 + f(x) - f^{k-1}(f(x)) \ge 0 \rightarrow f^{k-1}(f(x)) \in \{f(x), f(x) + 1\}.$$
We want to prove that $f(1) = 2$. Assume the contrary, by lemma 2, there is no $k$ such that $f^{k-1}(f(x)) = f(x)$, so we have
$$\forall x \in \mathbb{N}: f^{k-1}(f(x)) = f(x) + 1 \quad (1)$$
Set $t = k - 1$ then 1 tells us that for each $a$ in the range of $f$, we have $f^t(a) = a + 1$. If we use this for $a + 1$ we have $f^{2t}(a) = f^t(a + 1) = a + 2$. Therefore for every natural number $n$ we have
$$f^{nt}(a) = a + n$$
Hence $\{f^{nt}(a)\}$ which is a proper subset of $f^m(a)$ contains every big enough natural number. This contradicts the fact that members of $f^m(a)$ are distinct. So we should have $f(1) = 2$. Now 1 implies that $f(f(x)) = x+1$, by induction we have $f(x) = x + 1$.