㉑ 周期・余り（mod）を書き出して見つける
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
漸化式が『直前の k 項だけで次が決まる』なら、連続 k 項の組が一度再登場した瞬間から先は完全に繰り返す。余り（mod m）を取れば組の種類は有限個なので、必ずいつか再登場する。だから周期は予想ではなく『同じ組が出た』ことで証明できる。a(n+1) = 1/(1 − a(n)) のように値そのものが周期的になる分数型もある。
こんなときに使う
- a(2026) を 7 で割った余り、のように大きな添字の余りを問う
- a(n) がすべて整数であることを示せ、隣り合う項が互いに素であることを示せ
- 分数型で数項書くと元に戻る
- 一般項は求まるが、余りの計算には漸化式のまま使う方が楽
手順
- 1. 漸化式を mod m で書き直し、初項から順に余りを書き出す
- 2. 連続する（漸化式の階数分の）項の組が最初の組と一致したところで周期を確定させる
- 3. 『直前の項だけで次が決まるので、以後この繰り返し』と根拠を書く
- 4. 添字を周期で割った余りから答える
例題
a(1) = a(2) = 1、a(n+2) = a(n+1) + a(n) のとき a(2026) を 3 で割った余りを求めよ。
解答
- mod 3 で書き出す：a(1)〜a(10) は 1, 1, 2, 0, 2, 2, 1, 0, 1, 1
- (a(9), a(10)) = (1, 1) = (a(1), a(2))。次の項は直前の2項だけで決まるので、以後は周期8で繰り返す
- 2026 = 8·253 + 2 なので a(2026) ≡ a(2) ≡ 1
- ∴ 余りは 1
別解・ほかの見方
- 値そのものの周期：a(1) = 2、a(n+1) = 1/(1 − a(n)) は 2, −1, 1/2, 2, … で周期3
- 互いに素の証明：gcd(a(n+1), a(n)) = gcd(a(n), a(n−1)) = … = gcd(a(2), a(1)) とユークリッドの互除法で遡る
- 整数性の証明：一般項が無理数を含んでも（フィボナッチ）、漸化式から帰納法で整数と示す
- mod m の周期は m によって変わる（フィボナッチは mod 2 で3、mod 3 で8、mod 5 で20）
落とし穴
- 2項間なら1項、3項間なら2項の組が一致したことを確認せずに周期を主張する
- 周期の途中から始まる（前周期がある）場合に、添字の割り算がずれる
- 書き出しの計算ミスで偽の周期を見つける（2周期分書いて確認する）
- 周期を『予想』しただけで終わる（同じ組が再登場したことを根拠にする）
なぜ大事か
一般項が求まらない・不要なとき、余りや値を書き出して周期を見つける。整数問題との融合で東大頻出
東大での出方
東大は数列と整数の融合を好み、余り・互いに素・整数性が頻出テーマ。⑩〜⑮で一般項を出すより、漸化式のまま mod で扱う方が速いことが多い。
確認問題
- a(1) = 1、a(n+1) = 3a(n) + 1 を 5 で割った余りの周期を求めよ（答：1, 4, 3, 0, 1, … で周期4）
- a(1) = 2、a(n+1) = 1/(1 − a(n)) のとき a(100) を求めよ（答：2）
発展
mod m で2項間なら組は m² 通りしかないので、周期は必ず m² 以下（鳩の巣原理）。漸化式が逆向きにも解けるなら、前周期なしの純周期になる。
前提になるノード
「漸化式」のノード
- ⑩ 特性方程式型 a(n+1)=p·a(n)+q
- ⑪ 指数型 a(n+1)=p·a(n)+rⁿ（rⁿ⁺¹で割る）
- ⑫ nの多項式型 a(n+1)=p·a(n)+(An+B)
- ⑬ 分数型（逆数をとる） a(n+1)=a(n)/(p·a(n)+q)
- ⑭ 積・累乗型（対数をとる） a(n+1)=q·a(n)^p
- ⑮ 隣接3項間 a(n+2)+p·a(n+1)+q·a(n)=0
- ⑯ 連立漸化式（和と差・消去）
- ⑰ 和S(n)と一般項の混在型
- ⑱ 一次分数変換型 a(n+1)=(p·a(n)+q)/(r·a(n)+s)
- ⑲ 三角関数置換型 a(n+1)=2a(n)²−1
- ⑳ 偶奇分け（(−1)ⁿ型・2つ飛び）
- ㉑ 周期・余り（mod）を書き出して見つける
- 漸化式の型別処理（等比型・特性方程式・分数型・連立）
- ㉔ 推測＋数学的帰納法（誘導のない漸化式）
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。