初期条件の数、保存則、有限状態の周期性を区別して論証します。
1．帰納法は「次が決まる情報」に合わせる
1つ前の項から次項が決まる漸化式なら、通常は1つの初期値と1段の帰納法が対応します。$a_{n+2}$ が $a_n,a_{n+1}$ に依存するなら、2つの初期値を確認し、隣り合う2項についての仮定から次へ進みます。必要なのは形式的な「$n=k$ と仮定」ではなく、次の段で実際に使う情報です。
例題1：不等式を帰納的に保つ
$a_1=1,\ a_{n+1}=(a_n+3)/2$ なら、$a_n<3$ から $a_{n+1}<3$。また $3-a_{n+1}=(3-a_n)/2$ なので、より強い命題 $3-a_n=2^{2-n}$ も証明できます。弱い評価で十分な場合もあれば、差の式をそのまま保存すると正確な一般項になる場合もあります。
2．不変量は次項を代入して確かめる
例題2：整数解を作る保存則
$a_1=2,b_1=1,\ a_{n+1}=2a_n+3b_n,\ b_{n+1}=a_n+2b_n$ とします。展開すると、$$(2a+3b)^2-3(a+2b)^2=a^2-3b^2.$$ 初期値で $a_1^2-3b_1^2=1$ なので、全ての $n$ で $a_n^2-3b_n^2=1$。また正整数性も帰納的に保たれます。これにより方程式 $x^2-3y^2=1$ の正整数解が次々に得られますが、この議論だけで「全ての正整数解を尽くす」とまでは言えません。
3．有限状態は「やがて周期的」を保証する
有限集合 $X$ 上で $x_{n+1}=F(x_n)$ と、同じ規則で次の状態が決まるとします。状態が $M$ 個なら、$M+1$ 回の観測までに同じ状態が再登場し、その後は同じ道をたどります。保証されるのは途中からの周期性です。さらに $F$ が単射なら、同じ状態を逆向きにもたどれるため、初期状態から周期的になります。
例題3：途中まで周期に入らない
$a_1=1,\ a_{n+1}=2a_n$ の余りを法4で見ると、1,2,0,0,…。有限状態でも初項から周期的ではありません。法4では2倍する写像が単射でないためです。
例題4：3項間では2項を状態にする
$a_{n+2}=a_{n+1}+a_n$ の余りを法 $m$ で見ると、1項だけでは次が決まりません。状態 $(a_n,a_{n+1})$ を使い、$(x,y)\mapsto(y,x+y)$ とします。逆写像 $(u,v)\mapsto(v-u,u)$ があるので、初項から周期的です。状態数は $m^2$。周期は高々 $m^2$ ですが、常に $m^2$ という意味ではありません。
4．数項の実験と一般の証明を分ける
同じ余りが1回出ただけで証明できるのは、その余りだけで次が決まる場合です。規則が $n$ に依存するなら、係数の位相なども状態に含める必要があります。有限個の位相に収まらない任意の $n$ 依存の規則に、有限状態の結論を無条件では使えません。
作問者の視点――条件と解法の関係
確認演習と解答
まず方針と必要な条件を言葉にしてから計算してください。解答は開いて確認できます。
演習1 $a_1=1,\ a_{n+1}=2a_n+1$ の法5での最小周期を求めよ。
解答・考え方を開く
1,3,2,0,1,…。4つの異なる値の後に初期状態へ戻るので最小周期4。写像は法5で逆に戻れます。
演習2 $a_1=1,a_2=3,\ a_{n+2}=a_{n+1}+a_n$ の法5での最小周期を求めよ。
解答・考え方を開く
1,3,4,2,1,3,…。状態 $(1,3)$ が4段後に戻ります。最初の4値が異なるので最小周期4。
演習3 例題2から得られる2番目、3番目の整数解を求めよ。
解答・考え方を開く
$(a_2,b_2)=(7,4)$、$(a_3,b_3)=(26,15)$。それぞれ $49-48=1$、$676-675=1$。
関連する解説
既存の演習：問題#B013（法5での周期の証明）
参考資料
定理・基本的な方法の確認に使える公開教材です。本ページの例題・演習・作問上のコメントは、解説用に独自に構成しています。