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} となることを証明せよ。
ステップ 5/9: 正規化した数列も同じ漸化式を満たす
前のステップ次のステップ
bn=max⁡1≤k≤n−1(bk+bn−k)b_n=\max_{1\le k\le n-1}(b_k+b_{n-k})
詳しい解説

n>sn>s では元の漸化式から qnqn を引き、qk+q(n−k)=qnqk+q(n-k)=qn なので bn=max⁡1≤k≤n−1(bk+bn−k)b_n=\max_{1\le k\le n-1}(b_k+b_{n-k}) を得る。初期値と合わせれば、この漸化式により各 bnb_n も i≤si\le s の bib_i の和に展開できる。