MathLabs

第6問

a1,a2,a3,…a_1,a_2,a_3,\ldots を正の実数からなる数列とする。ある正整数 ss に対して、すべての n>sn>s で an=max⁡{ak+an−k∣1≤k≤n−1}a_n=\max\{a_k+a_{n-k}\mid 1\le k\le n-1\} が成り立つと仮定する。ℓ≤s\ell\le s を満たす正整数 ℓ\ell と正整数 NN が存在して、すべての n≥Nn\ge N で an=aℓ+an−ℓa_n=a_\ell+a_{n-\ell} となることを証明せよ。
ステップ 7/9: 各剰余類の部分列は安定する
前のステップ次のステップ
bn≥bn−ℓ,bs+t,bs+t+ℓ,bs+t+2ℓ,…b_n\ge b_{n-\ell},\qquad b_{s+t},b_{s+t+\ell},b_{s+t+2\ell},\ldots
詳しい解説

すべての n>sn>s で、漸化式と bℓ=0b_\ell=0 から bn≥bn−ℓb_n\ge b_{n-\ell} が得られる。したがって各 1≤t≤ℓ1\le t\le\ell について、数列 bs+t,bs+t+ℓ,bs+t+2ℓ,…b_{s+t},b_{s+t+\ell},b_{s+t+2\ell},\ldots は非減少である。ステップ6より値は有限集合に属するので、各数列は最終的に一定になる。有限個の部分列の安定化閾値の最大を取れば、ある NN が存在してすべての n≥Nn\ge N で bn=bn−ℓb_n=b_{n-\ell} となる。