Proving that $f(n)=n$ if $f(n+1)>f(f(n))$ How can we prove that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is a function so that $f(n+1)>f(f(n))$ for all $n\in\mathbb{N}$ then $f(n)=n$ for all $n\in\mathbb{N}$?
This is problem 6 from the IMO 1977. I found it in this book.
 A: Another proof :

*

*We first show the property $P_n$ is true for all $n$
$\\$ $P_n : (\forall k \geq n \implies f(k) \geq n)$
Proof by Induction :
(i) $P_0$ is true, since $\forall k \geq 0 ( f(k) \geq 0)$
(ii) $\forall n$, if $P_n$ is true, then
$\forall k \geq n+1 ; k-1 \geq n$ then $f(k-1) \geq n$ then $f(f(k-1)) \geq n$ and
$f(k) > f(f(k-1)) \geq n$ thus $f(k) \geq n+1$
Therefore $P_{n+1}$ is true.


*$\forall n$, since $P_n$ is true, take $k=n$, then $f(n) \geq n$


*Then $\forall n, f(f(n)) \geq f(n)$ then the starting hypothesis yields:
$\\$ $f(n+1)>f(n)$ then $f$ is strictly growing.
Thus the starting hypothesis implies : $\forall n, n+1> f(n)$


*Thus for all $n$, $n+1>f(n)>=n$. Hence, $f(n) = n$
A: Claim 1: If $f(k) = 0$ then $k =0$.
Proof: Suppose not.  Then there exists $k$ such that $0 = f(k) > f(f(k-1))$, which is not possible, as $f: \mathbb{N} \mapsto \mathbb{N}$.
Claim 2: $f(0) = 0$.
Proof: Let $S = \{f(k) | k > 0\}$.  Let $a$ be the smallest number in $S$.  Then there exists $k >0$ such that $a = f(k) > f(f(k-1))$.  But this means $f(k-1) = 0$.  Thus $k=1$, and $f(0) = 0$.  
Claim 3: $f(n) = n$.
Proof: Assume, for all $0 \leq m < n$, that $f(k) = m$ iff $k = m$.  Now we proceed as in the proofs of Claims 1 and 2.
If $f(k) = n$, then $f(f(k-1)) < n$, which means $k-1 = f(k-1) = f(f(k-1)) < n$.  So $k < n+1$, which means that $k = n$.
Let $S = \{f(k) | k > n\}$.  Let $a$ be the smallest number in $S$.  Thus there exists $k >n$ such that $a = f(k) > f(f(k-1))$.  Therefore $f(k-1) \leq n$.  But if $f(k-1) < n$, then $f(k-1) = k-1$, and so $k \leq n$.  But $k>n$.  Therefore, $f(k-1) = n$, and so $k= n+1$ and $f(n) = n$. 
A: Attempted solution (Improvements/corrections are greatly welcome!):
Clearly, the function isn't constant on any interval. So it must be either strictly increasing or strictly decreasing. 
Suppose the function isn't injective. Then there exist $a,b \in \mathbb{N}$ such that $f(a) = f(b)$, but $a \neq b$. So either $a>b$ or $a<b$. WLOG, let $a>b$. Then $a = b+m$, for some $m \in \mathbb{N}$. Now, $f(a) = f(b+m) > f(f(b+(m-1)) > f(f(f(b+m-2) > ... >f(f(...(f(b))...)$. Now, suppose, WLOG that $f$ is increasing (if $f$ is decreasing, then there is also a contradiction). Then $f(f(...(f(b))...) > f(b)$. But $f(b) = f(a)$. Thus, we have a contradiction. So, $f$ must be injective.
Now, apply $f^{-1}$ on both sides, and you get that $n+1 > f(n)$, $\forall n \in \mathbb{N}$. 
Clearly, if $ \forall n \in \mathbb{N}$, $f(n) = a*n+b$, where $a \neq 1$ and $b \neq 0$, then it would contradict $n+1 > f(n)$, $\forall n \in \mathbb{N}$.
Now it's just left to see what happens if there exists an $n'$ where $f(n') \neq n'$. In such a case, $f(n')>n'$ or $f(n')<n'$. Check that both cases still lead to contradictions.
I think if you can somehow rule out that $f$ is decreasing, then this might work. 
