Problem 6

Let

f:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}

. Prove that if

f(n+1)>f(f(n))

for every positive integer

n

, then

f(n)=n

for every positive integer

n

Step 4 of 5: Use the original inequality

In plain words

A value above the diagonal makes strict increase contradict the given inequality.

f(m)\ge m+1\Longrightarrow f(f(m))\ge f(m+1)

Detailed analysis

If $f(m)\ge m+1$ , strict increase gives $f(f(m))\ge f(m+1)$ . But the hypothesis says $f(m+1)>f(f(m))$ , a contradiction. Hence $f(m)\le m$ .