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 1 of 5: Establish the first tail minimum

Previous step Next step

In plain words

The inequality prevents every later term from attaining the minimum.

f(m)>f(f(m-1))\quad(m>1)

Detailed analysis

For $m>1$ , apply the hypothesis at $m-1$ . Then $f(m)$ is strictly greater than another value of the sequence, so it cannot be the minimum of the whole set. Positive integers are well ordered; therefore the unique minimum is $f(1)$ .