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。
第 2/5 步：对尾序列最小值作归纳
上一步下一步
通俗地说

去掉已确定的前段后，重复首个尾序列的论证。

Sn:f(n)<f(m) for every m>nS_n: f(n)<f(m)\text{ for every }m>n
详细分析

假设 SnS_n 以及此前已证明的所有尾序列最小值命题。当 m>n+1m>n+1 时，由 f(m−1)>f(n)f(m-1)>f(n) 得 SnS_n。此前命题还给出 f(n)>f(n−1)>⋯>f(1)≥1f(n)>f(n-1)>\cdots>f(1)\ge1，故 f(n)≥nf(n)\ge n，从而 f(m−1)≥n+1f(m-1)\ge n+1。所以 f(m−1)f(m-1) 是从 n+1n+1 开始的尾序列中的索引。题设给出 f(m)>f(f(m−1))f(m)>f(f(m-1))，因此 f(m)f(m) 不是该尾序列的最小值。最小值必存在，于是它唯一地等于 f(n+1)f(n+1)，即 Sn+1S_{n+1} 成立。