大学入試数学 二段進む数学的帰納法—偶奇それぞれの初期値から全体を覆う｜武蔵野個別指導塾

n から n+2 へ進む証明では、起点を一つだけ確かめると片方の偶奇が抜けます。二本の鎖がどこでつながるかを余りの表から読み解けば、二本を別々に埋める進め方が二段です。

よくあるのは、次のような場面です。演習の解き直しをしていた高校生が、n=1 の場合だけを確かめ、そのあと n から n+2 へ進む計算を一行書いて、「これで偶数の場合も示せました」と答案を閉じました。式の変形そのものは合っています。足りないのは、二つ目の起点です。翌日に自分の答案を読み返すと、n が偶数のときの欄だけが白いままでした。二つ進む帰納法では、推論の型より先に、起点をいくつ置くかで答案の正しさが決まります。

一、二段進む証明が顔を出す三つの形

整数の証明では、n を一つずつ増やす帰納法のほかに、二つずつ増やす帰納法が登場します。二つずつ進む型は、次の三つのどれかの形で現れます。

第一は、余りや偶奇で結論が二通りに分かれる命題です。2 の n 乗を 3 で割った余りのように、n の偶奇によって値が入れ替わるものを扱います。片方の偶奇だけで確かめて満足すると、もう片方が抜けます。

第二は、漸化式が同じ偶奇の項だけを結ぶ数列です。aₙ₊₂ を aₙ から決める式では、番号の差が 2 なので、番号を一つ飛ばしにした列が二本できます。二本の列は互いに交わらないので、それぞれに起点が要ります。

第三は、n と n+2 の差をとると共通の因数が現れる式です。(n+3)(n+5) のように二つ離れた数を掛けた形では、n を n+2 に置き換えた差がくっきりします。差がまとまると、余りや倍数の話へ持ち込みやすくなります。

二つ進む型が入試で問われるのは、周期が 2 の現象が多いからです。余りが交互に入れ替わる、偶奇で符号が変わる、同じ偶奇の項だけが漸化式で結ばれる、といった場面です。周期が 2 なら、番号を 1 増やすと性質が変わり、2 増やすと元に戻ります。だから推論も 2 ずつ進めるのが自然になります。

問題文の言い方にも手がかりがあります。n が奇数のとき、n が偶数のとき、と場合が二つに分かれていれば、鎖も二本と考えられます。漸化式が aₙ₊₂ を aₙ から決める形なら、番号の差が 2 なので鎖は二本です。反対に、aₙ₊₁ を aₙ から決める形なら鎖は一本で、起点も一つです。式の形を見れば、問題文の言葉に頼らずに鎖の本数を決められます。

どの形でも、最初に見る整数条件は二つです。一つは起点をいくつ置くか、もう一つは推論が結ぶ番号の差です。差が 2 なら起点は二つ、差が 3 なら起点は三つになります。この二つを答案の最初に決めてから式を書き始めると、片方の偶奇が抜ける事故を防げます。

二、二つの起点が要る理由

整数 n についての命題を P(n) と書きます。P(n) が n₀ 以上のすべての整数で成り立つことを示すとき、次の二つを確かめるのが二段の帰納法です。

(i) P(n₀) と P(n₀+1) が成り立つ。
(ii) n₀ 以上のすべての整数 k について、
     P(k) が成り立てば P(k+2) が成り立つ。

この二つがそろうと、n₀ 以上のすべての整数 n で P(n) が成り立ちます。理由は番号を二本の鎖に分けると見えます。n₀ から始めて n₀+2、n₀+4 と進む鎖と、n₀+1 から始めて n₀+3、n₀+5 と進む鎖です。整数は偶数か奇数かのどちらかなので、n₀ 以上の整数は必ずこの二本のどちらかに入ります。一本目の鎖は P(n₀) を起点に (ii) を繰り返して埋まり、二本目の鎖は P(n₀+1) を起点に埋まります。だから起点は二つ要ります。

この理由は、背理法の形でも書けます。n₀ 以上の整数で P(n) が成り立たないものがあると仮定し、そのような最小の n を m とします。m は n₀ 以上なので、m と n₀ の差は偶数か奇数かです。差が偶数なら m は n₀ と同じ鎖にあり、m から 2 ずつ下がるとやがて n₀ に着きます。差が奇数なら n₀+1 に着きます。どちらの場合も、着いた先は (i) で確かめた起点です。鎖を下がる各段は (ii) の対偶なので、成り立たない項から下がると、成り立たない項が続きます。ところが起点では成り立っているので、矛盾します。したがって、成り立たない n は存在しません。

ここで使った (ii) の対偶は、P(k+2) が成り立たなければ P(k) も成り立たない、という形です。答案では (ii) をそのまま書くのが標準ですが、鎖を下る説明をしたいときは対偶の形が便利です。

起点の組み合わせを間違える例も多いです。n₀ と n₀+2 を確かめてしまうと、n₀+1 がどの鎖の起点にもならず、偶数と奇数のうち片方が抜けます。二つ並べるなら、必ず番号が 1 違いの二つにします。n₀ と n₀+2 は同じ鎖の隣どうしなので、鎖の本数は増えません。

起点を一つに減らすと何が起きるかを考えます。P(n₀) だけを確かめて (ii) を繰り返すと、埋まるのは n₀、n₀+2、n₀+4 という一本の鎖だけです。もう一本の鎖は最初の一段が空いたままなので、何段推論を重ねても埋まりません。答案にすべての n で成り立つと書いた瞬間に、この空きが論理の穴になります。

図1のように、起点と、そこから届く番号を並べて確かめると、二本の鎖がそろっているかを見落としません。まず起点を二つ書き、それぞれの右に番号を三つずつ並べます。二列が途切れずに伸びていれば、覆えていない番号はありません。

図1のように、起点 1 からは 1、3、5 が届き、起点 2 からは 2、4、6 が届きます。二つを並べて初めて、すべての正の整数が視野に入ります。

一段の帰納法との違いも整理します。一段の帰納法は P(k) から P(k+1) を導く型で、起点は一つで足ります。二段の帰納法は P(k) から P(k+2) を導く型で、起点が二つ要ります。どちらも起点を確かめ、推論を繰り返すという骨格は同じです。変わるのは推論が結ぶ番号の差で、差が d なら起点は d 個になります。三つずつ進む型なら起点は三つで、三本の鎖が並びます。

起点の選び方にも決まりがあります。命題が成り立つ範囲の最小の整数を n₀ として、n₀ と n₀+1 を確かめます。範囲が n ≥ 2 なら 2 と 3、n ≥ 3 なら 3 と 4 です。小さいほうだけを確かめて済ませると二本目の鎖が空きます。逆に、範囲の外の数を起点にすると、その数では命題が成り立たないことがあるので、鎖の途中に偽の項が混ざります。起点は範囲の中で選ぶのが原則です。

三、基本例題　2 の n 乗を 3 で割った余り

（標準）n を正の整数とします。2 の n 乗を 3 で割った余りを、n が奇数のときと偶数のときに分けて求めてください。答えは「n が奇数のとき 2、偶数のとき 1」の形で書き、そのことを二段の帰納法で示してください。

まず小さい数で様子を見ます。2¹ = 2 なので、n=1 のとき余りは 2 です。2² = 4 = 3·1 + 1 なので、n=2 のとき余りは 1 です。2³ = 8 = 3·2 + 2 なので、n=3 のとき余りは 2 です。2⁴ = 16 = 3·5 + 1 なので、n=4 のとき余りは 1 です。余りが 2 と 1 を交互に繰り返すと予想できます。

示す命題は「2 の n 乗を 3 で割った余りは、n が奇数のとき 2、偶数のとき 1」です。整数を 3 で割った余りは 0、1、2 のどれかで、2 の n 乗は 3 の倍数ではないので、余りは 1 か 2 に限られます。答案では、2 の k 乗 = 3q + r と置くときに、r が 0、1、2 のどれかであることと、q が整数であることを一行で断っておくと、文字の意味がぶれません。

1. 起点

n=1 のとき、2¹ = 2 なので余りは 2 です。n=2 のとき、2² = 4 = 3·1 + 1 なので余りは 1 です。

2. 推論

k を 1 以上の整数とし、2 の k 乗を 3 で割った余りが r であると仮定します。このとき、2 の k 乗 = 3q + r（q は整数、r は 0、1、2 のどれか）と書けます。

2 の k+2 乗
= 4·(2 の k 乗)
= 4(3q + r)
= 12q + 4r
= 3(4q + r) + r

最後の行で、4r を 3r + r に分けています。3(4q + r) は 3 の倍数なので、2 の k+2 乗を 3 で割った余りも r です。つまり、番号を 2 増やしても余りは変わりません。

この分け方は、4 と 3 の差が 1 であることから来ています。4r をそのまま残すと、余りの範囲を超えてしまうので、3 の倍数の部分を商へ移し、残りを新しい余りにします。法が変われば、この移し方も変わります。5 で割る問題なら 4r を 5 の倍数と残りに分ける、というように、法に合わせて分け直します。

3. まとめ

奇数は 1 から 2 ずつ進んで届き、偶数は 2 から 2 ずつ進んで届きます。起点で余りが 2 と 1 に分かれ、推論で余りが保たれるので、奇数では常に 2、偶数では常に 1 です。

確認として、2⁵ = 32 = 3·10 + 2、2⁶ = 64 = 3·21 + 1 で、予想と一致します。

図2に、n と余りの対応を並べました。横に番号を並べると、余りが交互に入れ替わる様子が見えます。

図2のように、n を 2 増やしても余りは同じ列に残ります。2 と 1 の列がそれぞれ縦に続くので、二本の鎖がそのまま見えます。

四、標準例題　同じ偶奇だけを結ぶ漸化式

（やや難）数列 a₁ = 1、a₂ = 3、aₙ₊₂ = 2aₙ + 3（n = 1、2、3、…）を定めます。すべての項 aₙ が奇数であることを示してください。

この漸化式は、番号を 2 増やした項を、同じ偶奇の前の項から決めています。a₃ は a₁ から、a₄ は a₂ から決まり、aₙ と aₙ₊₁ を結ぶ式はありません。したがって推論は n から n+2 へ進み、起点は二つ要ります。

この漸化式を n から n+1 の型で書こうとしても、aₖ₊₁ を aₖ だけから決める式がありません。aₖ₊₂ を決めるには aₖ が要り、aₖ₊₁ を決めるには aₖ₋₁ が要ります。つまり、番号を 1 増やす推論は、二つの項を同時に持たないと書けません。二段の型は、この一つ飛ばしの関係をそのまま答案にする型です。

1. 起点

a₁ = 1 は奇数です。a₂ = 3 も奇数です。

2. 推論

k を 1 以上の整数とし、aₖ が奇数であると仮定します。奇数の 2 倍は偶数なので、2aₖ は偶数です。偶数に 3 を足すと奇数になるので、aₖ₊₂ = 2aₖ + 3 は奇数です。

3. まとめ

奇数番目の項は a₁ から、偶数番目の項は a₂ から、それぞれ推論を繰り返せば奇数だとわかります。よってすべての項は奇数です。

確認として、a₃ = 2·1 + 3 = 5、a₄ = 2·3 + 3 = 9、a₅ = 2·5 + 3 = 13、a₆ = 2·9 + 3 = 21 で、いずれも奇数です。

補足します。この問題では、実は aₖ が奇数という仮定を使わずに推論が済みます。2aₖ が偶数になることは、aₖ がどんな整数でも成り立つからです。それでも起点が二つ要るのは、推論が番号を 2 ずつしか進めないからです。仮定が弱くても、鎖の本数は減りません。この点を取り違えて、仮定を使っていないから起点は一つでよいと考える答案がよくあります。

別の見方も書きます。mod 2 で見ると、aₖ₊₂ = 2aₖ + 3 ≡ 0 + 1 ≡ 1 です。番号を 2 増やすと必ず 1 になり、aₖ の値によらず奇数です。この形は計算が短い代わりに、どの番号から出発したかを答案から消しやすいので、起点の確認を別に書いておくと安全です。

五、発展例題　成り立つ n を絞る

（難）n を正の整数とします。2 の n 乗 + 3 の n 乗が 5 の倍数になる n をすべて求めてください。

aₙ = 2 の n 乗 + 3 の n 乗とおきます。番号を 2 増やしたときの変化を見ます。

aₙ₊₂
= 2 の n+2 乗 + 3 の n+2 乗
= 4·(2 の n 乗) + 9·(3 の n 乗)
= 4·(2 の n 乗) + 4·(3 の n 乗) + 5·(3 の n 乗)
= 4aₙ + 5·(3 の n 乗)

したがって aₙ₊₂ ≡ 4aₙ (mod 5) です。4 と 5 は互いに素なので、4aₙ が 5 で割り切れることと aₙ が 5 で割り切れることは同じです。つまり、鎖の上では 5 で割り切れるかどうかが変わりません。

4 と 5 が互いに素であることは、この言い換えの要です。もし 4 が 5 の倍数なら、aₙ が 5 の倍数でなくても 4aₙ は 5 の倍数になり、鎖の上で性質が保たれません。法と掛け算の数が互いに素かどうかを、答案の一行として確かめてください。互いに素でない場合は、割り切れるかどうかではなく、余りそのものを鎖に沿って追うことになります。

1. 起点

n=1 のとき、a₁ = 2 + 3 = 5 なので 5 の倍数です。n=2 のとき、a₂ = 4 + 9 = 13 なので 5 の倍数ではありません。

2. まとめ

奇数番目の鎖は a₁ から始まり、a₁ が 5 の倍数なので、すべての奇数 n で aₙ は 5 の倍数です。偶数番目の鎖は a₂ から始まり、a₂ は 5 の倍数ではありません。鎖の上で 5 の倍数かどうかは変わらないので、すべての偶数 n で aₙ は 5 の倍数ではありません。よって、5 の倍数になるのは n が奇数のときだけです。

確認します。n=3 では 8 + 27 = 35 = 5·7 です。n=4 では 16 + 81 = 97 で、97 を 5 で割った余りは 2 です。n=6 では 64 + 729 = 793 で、余りは 3 です。偶数番目では余りが 2 と 3 を往復しており、0 にはなりません。

この往復は、答案にも一行で書けます。a₂ の余りは 3、a₄ の余りは 4·3 = 12 を 5 で割った余り 2、a₆ の余りは 4·2 = 8 を 5 で割った余り 3 です。0 が現れないことを、最初の二項で示しておくと、鎖全体で 0 にならないことが見えます。

補足します。すべての n で成り立つという形と、成り立つ n を求める形では、二つ目の起点の役割が変わります。前者では二つ目の起点も成り立つことを確かめますが、後者では二つ目の起点が成り立たないことを示す材料になります。どちらの場合も、起点を二つ並べて初めて、二本の鎖の行き先を別々に言えます。

六、誤答の実例と直し方

次の答案は、n=1 だけを確かめて全体を結論した例です。

n=1 のとき 2 の 1 乗 = 2 で、2 を 3 で割った余りは 2 である。
n を k から k+2 に進めても、4·(2 の k 乗) = 3·(4q + r) + r なので
余りは変わらない。よってすべての正の整数 n で余りは 2 である。

原因は三つあります。第一に、起点が一つしかありません。n=2 の確認が抜けているので、偶数番目の鎖が空いています。第二に、結論のすべての n で余りは 2 という部分が、n=2 の実際の値 1 と食い違っています。小さい数で確かめれば気づけた食い違いです。第三に、推論の中で余りが r と文字で置いたのに、最後に r を 2 に固定してしまっています。文字で置いた以上、r が何であっても余りが保たれる、という形で結論を出す必要があります。

直し方は、起点を二つに増やし、鎖ごとに結論を分けることです。

(i) n=1 の余りは 2、n=2 の余りは 1 である。
(ii) 番号を 2 増やしても余りは変わらない。
(iii) 奇数は 1 の鎖、偶数は 2 の鎖に入るので、
     奇数では 2、偶数では 1 である。

図3に、一本の鎖だけを塗った答案と、起点を足した答案を並べました。左が元の答案、右が直した答案です。

図3のように、左の答案は一本の鎖しか塗れていません。右のように起点 2 を足すと、抜けていた 2、4、6 が埋まります。答案を読み直すときは、起点の数と鎖の本数を指で数えると早く見つかります。

もう一つのよくある誤りは、起点を n=1 と n=3 にしてしまうことです。1 と 3 は同じ奇数側の鎖なので、鎖は一本しか増えません。n=2 が抜けたままです。起点を二つ書いたから安心するのではなく、二つの起点の番号が 1 違いであるかを見ます。

三つ目は、推論で示したことが k から k+1 になっている誤りです。式を書いたつもりが、番号を 1 だけ増やした差を計算していると、鎖の本数が変わります。推論の行では、左辺と右辺の番号の差を声に出して確かめると防げます。差が 2 のつもりで 1 の計算を混ぜると、答案の結論と起点の数がちぐはぐになります。

四つ目は、推論の中で結論を使ってしまう誤りです。示したい式を仮定として書き、その式を変形して終わると、何も示していません。推論で使ってよいのは、番号が 2 小さい項についての仮定だけです。答案では、仮定の行と、仮定を使って変形した行を分けて書くと、使い方が見えます。

七、練習問題

次の五問を解いてください。例題とは数も場面も変えてあります。

練習1（標準）すべての正の整数 n について、4 の n 乗を 5 で割った余りは、n が奇数のとき 4、偶数のとき 1 であることを示してください。

練習2（標準）数列 b₁ = 5、b₂ = 7、bₙ₊₂ = 5bₙ + 2（n = 1、2、3、…）のすべての項が奇数であることを示してください。

練習3（やや難）すべての正の整数 n について、3 の n 乗を 8 で割った余りは、n が奇数のとき 3、偶数のとき 1 であることを示してください。

練習4（やや難）すべての正の整数 n について、n² + 2n を 4 で割った余りは、n が奇数のとき 3、偶数のとき 0 であることを示してください。

練習5（難）正の整数 n について、2 の n 乗 + 9 の n 乗が 11 の倍数になる n をすべて求めてください。

八、練習問題の答えと解き方

練習1 番号を 2 増やしたときの変化を見ます。4 の k+2 乗 = 16·(4 の k 乗) = (15 + 1)·(4 の k 乗) = 15·(4 の k 乗) + 4 の k 乗です。15·(4 の k 乗) は 5 の倍数なので、4 の k+2 乗を 5 で割った余りは 4 の k 乗の余りと同じです。起点は n=1 で 4、n=2 で 16 = 5·3 + 1 なので 1 です。奇数は 1 の鎖、偶数は 2 の鎖に入るので、奇数では 4、偶数では 1 です。

練習2 起点は b₁ = 5 と b₂ = 7 で、どちらも奇数です。bₖ が奇数なら、5bₖ は奇数で、奇数に 2 を足しても奇数なので、bₖ₊₂ = 5bₖ + 2 は奇数です。奇数番目は b₁ から、偶数番目は b₂ から埋まるので、すべての項が奇数です。

練習3 3 の k+2 乗 = 9·(3 の k 乗) = (8 + 1)·(3 の k 乗) なので、8 で割った余りは変わりません。起点は n=1 で 3、n=2 で 9 = 8 + 1 なので 1 です。よって奇数では 3、偶数では 1 です。

練習4 (k+2)² + 2(k+2) = k² + 4k + 4 + 2k + 4 = (k² + 2k) + 4k + 8 です。4k + 8 は 4 の倍数なので、4 で割った余りは k² + 2k の余りと同じです。起点は n=1 で 1 + 2 = 3、n=2 で 4 + 4 = 8 なので 0 です。奇数では 3、偶数では 0 になります。

練習5 aₙ = 2 の n 乗 + 9 の n 乗とおきます。aₙ₊₂ = 4·(2 の n 乗) + 81·(9 の n 乗) = 4aₙ + 77·(9 の n 乗) なので、aₙ₊₂ ≡ 4aₙ (mod 11) です。4 と 11 は互いに素なので、11 で割り切れるかどうかは鎖の上で変わりません。起点は n=1 で 2 + 9 = 11、n=2 で 4 + 81 = 85 = 11·7 + 8 です。奇数番目は 11 の倍数、偶数番目は 8 から始まり 0 にならないので、11 の倍数になるのは n が奇数のときだけです。n=3 では 8 + 729 = 737 = 11·67 で、確かに成り立ちます。

九、覚えておくこと

• 推論が結ぶ番号の差が 2 なら、起点は二つ要る。
• 差が d なら起点は d 個で、鎖も d 本になる。
• 起点は成り立つ範囲の最小の整数から、続けて二つ選ぶ。
• 一本の鎖は一つの偶奇しか覆わない。
• 結論がすべての n か成り立つ n を求めるかで、二つ目の起点の使い方が変わる。

十、つまずきの見分け方と確かめ方

答案に起点が一つしか書かれていないときは、まず n₀+1 の確認を足させます。そのうえで、起点の番号を二つ書かせ、それぞれから三項ずつ並べさせると、鎖が二本あることが目で見えます。推論の行では、番号が 2 ずつ進んでいるかを指でなぞり、差が 1 に戻っていないかを確かめます。結論の文では、すべての n と成り立つ n を求めるのどちらを聞かれているかを読み返させます。余りの問題なら、起点の二つの値と、鎖の上で余りが保たれる理由の二行がそろっているかを見ます。この四つの確認で、二段の帰納法の答案はほとんど崩れません。

式が長い問題では、差をとる計算を一行ずつ書かせます。aₙ₊₂ を展開し、aₙ の項と残りの項に分け、残りが法の倍数であることを示す、という三行です。この三行が書ければ、鎖の上で性質が保たれる理由を説明できます。逆に、展開を一気に書いてしまうと、どの項が法の倍数なのかが答案から消え、読み手が確かめられません。

数列の問題では、最初の三項を実際に計算させます。a₁、a₂、a₃ を手で出し、a₃ が a₁ と同じ鎖に入ることを確かめると、漸化式が一つ飛ばしで結ばれていることが実感できます。計算した三項が、答案の起点の二つと最初の推論の結果にそのまま対応します。

二本の鎖がそろった答案は、番号を一つ飛ばしても根拠が途切れません。