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 となる。