MathLabs

Problem 6

Let f:Z>0→Z>0f:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}. Prove that if f(n+1)>f(f(n))f(n+1)>f(f(n)) for every positive integer nn, then f(n)=nf(n)=n for every positive integer nn.
Step 3 of 5: Deduce strict increase
Previous stepNext step
In plain words

A positive strictly increasing integer sequence grows at least as fast as the identity.

n<m⟹f(n)<f(m)n<m\Longrightarrow f(n)<f(m)
Detailed analysis

The statements SnS_n for all nn say exactly that f(1)<f(2)<⋯f(1)<f(2)<\cdots. Since f(1)≥1f(1)\ge1, this implies f(m)≥f(1)+m−1≥mf(m)\ge f(1)+m-1\ge m.