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 2 of 5: Induct on tail minima

Previous step Next step

In plain words

Repeat the first-tail argument after removing the established initial segment.

S_n: f(n)<f(m)\text{ for every }m>n

Detailed analysis

Assume $S_n$ and all previously established tail-minimum statements. For $m>n+1$ , $f(m-1)>f(n)$ by $S_n$ . Also, the earlier statements give $f(n)>f(n-1)>\cdots>f(1)\ge1$ , so $f(n)\ge n$ and therefore $f(m-1)\ge n+1$ . Thus $f(m-1)$ is an index in the tail starting at $n+1$ . The hypothesis gives $f(m)>f(f(m-1))$ , so $f(m)$ is not the minimum in that tail. Its minimum exists, and hence it must be the unique value $f(n+1)$ , proving $S_{n+1}$ .