MathLabs

第6题

设 f:Z>0→Z>0f:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}。证明若对每个正整数 f(n+1)>f(f(n))f(n+1)>f(f(n)) 有 nn,则对所有正整数 f(n)=nf(n)=n 都有 nn。
第 3/5 步:推出严格递增
通俗地说

正整数严格递增数列的增长速度至少与恒等数列相同。

n<m⟹f(n)<f(m)n<m\Longrightarrow f(n)<f(m)
详细分析

所有 SnS_n(对每个 nn)正好说明 f(1)<f(2)<⋯f(1)<f(2)<\cdots。又因 f(1)≥1f(1)\ge1,所以 f(m)≥f(1)+m−1≥mf(m)\ge f(1)+m-1\ge m。