Interesting question about functions

Question

I saw the following question and I would like to share. I don't know the answer.

Suppose that the function $f:\Bbb{N}\to\Bbb{N}$ has the property $f(f(n))<f(n+1)$ for any $n\in\Bbb{N}$. Prove that $f(n)=n$.

Answer 1

Consider the set $A=\{ f ( f (1)), f (2), f ( f (2)), f (3), f ( f (3)),\ldots, f (n), f ( f (n)), . . .\}$.

That is the set of all numbers appearing in the inequality $f ( f (n)) < f (n + 1)$.

This set has a smallest element, which cannot be of the form $f (n + 1)$ because then it would be larger than $f ( f (n))$.

Thus it is of the form $f ( f (n))$.

The same argument shows that for this $n$, $f (n) = 1$.

If $n$ itself were greater than $1$, we would get $1 = f (n) > f ( f (n − 1))$, which is impossible. Hence, $f (1) = 1$ and $f (n) > 1$ for $n > 1$.

Considering the restriction $f : \{n \ge 2\} \to \{n \ge 2\}$, the same argument applied shows that $f (2) = 2$ and $f (n) > 2$ for $n > 2$. By induction, one shows that $f (k) = k$, and $f (n) > k$ for $n > k$, thus the unique solution to the problem is $f(n)=n$.