大学入試数学 数学的帰納法と合同条件—指数式の差を作って仮定が使える形へ直す｜武蔵野個別指導塾

4 の 2n+1 乗と 3 の n+2 乗の和が 13 で割り切れることを示すとき、仮定を使える形へ式を直す鍵は指数の差だ。

定期考査の解き直しをノートに写していた高校生が、正の整数 n について 4 の 2n+1 乗と 3 の n+2 乗の和が 13 で割り切れることを示す問題で、n+1 の場合の式を書いたまま止まっている。式変形は進んでいる。止まったのは、n の場合に成り立つと仮定したことを、n+1 の式のどこへ当てるかという一点である。ここで「n+1 の場合も 13 で割り切れる」と書き足すと、これから示す結論を仮定に混ぜた答案になり、n の場合の仮定は一度も使われないまま終わる。

指数を含む式の整除を帰納法で示すとき、答案の形はほぼ決まる。n+1 の式を、n の式の定数倍と、法で割り切れる式の和に分ける。この分け方を身につけると、どの項を基準の倍率にするか、どの係数が法を吸収するかが、計算だけで決まる。以下では、その分け方の作り方と、余りの周期を並べる直接の方法との使い分けを、自作の数で順に確かめる。

問われ方の三つの型と、最初に見る条件

この単元の設問は大きく三つの型に分かれる。どの型でも、答案の骨格は同じ四段である。

第一の型は、すべての正の整数 n について法 m が式を割り切ることを示す証明である。式の形は、指数が n の一次式になっている二項の和が多い。答案では、起点、仮定、推論、結論の四段をそろえ、推論の段で仮定を使った行を明示する。

第二の型は、n+1 の式を n の式で表す変形そのものを問うものである。帰納法の答案の途中を空欄にして、そこに入る等式を書かせる形で出る。ここで問われているのは計算の正確さだけでなく、どの項を基準の倍率にするかという選択である。基準の取り方を変えると、残る係数が変わり、法で割り切れるかどうかも変わる。

第三の型は、余りの周期を並べる方法と帰納法のどちらで書くかを選ばせるものである。法が小さいときは余りの表が数行で済むが、法が大きくなり周期が長くなると、表だけで答案の大半が埋まる。答案の長さと、条件を確かめた行をどこに残すかが判断の材料になる。

三つの型に共通して、最初に見るのは指数の増え方である。n が1増えるとき、4 の指数が2増えて 3 の指数が1増えるなら、それぞれ 16 倍と 3 倍になる。次に、その倍率の差と法の関係を見る。最後に、起点の n を式に入れて、法で割り切れるかを確かめる。この順番を変えると、計算の途中で何を示そうとしているのかが混ざり、答案の最後で結論と式が食い違う。

仮定が使える形とはどういう形か

整数 a, b と正の整数 m について、a − b が m の倍数であることを a ≡ b (mod m) と書く。m が a を割り切ることを m | a とも書く。定義をこの形で持っておくと、指数の計算をしたあとに「差が法の倍数か」へ戻して確かめられる。合同式の足し算と掛け算は、この定義から導ける。a ≡ b (mod m) なら a − b = ms、c ≡ d (mod m) なら c − d = mt と書ける。和の差は (a + c) − (b + d) = m(s + t) で m の倍数、積の差は ac − bd = c(a − b) + b(c − d) = m(cs + bt) で m の倍数である。指数についても、a ≡ b (mod m) なら aⁿ ≡ bⁿ (mod m) が、掛け算の性質を n 回使って示せる。

数学的帰納法は、正の整数 n についての命題 P(n) を、次の三段で示す。第一に P(1) が成り立つことを確かめる。第二に P(n) が成り立つと仮定する。第三に、その仮定を使って P(n+1) を示す。仮定に置けるのは P(n) だけである。P(n+1) はこれから示す結論であり、証明の途中で使ってよい対象ではない。この一点を外すと、答案は正しい式変形をしていても循環になる。

P(n) が「m は f(n) を割り切る」であるとき、P(n+1) を示すには f(n+1) が m の倍数だと示す。そのために、f(n+1) を次の形に書く。

f(n+1) = C・f(n) + m・G(n)

C と G(n) は整数である。この形なら、仮定から f(n) = mk と置けて、f(n+1) = m(Ck + G(n)) となる。Ck + G(n) は整数だから、m は f(n+1) を割り切る。つまり仮定が使える形とは、f(n) が定数倍で顔を出し、残りが法の倍数で書けている形のことである。仮定を使うのは C・f(n) の部分だけで、m・G(n) の部分は仮定を使わずに m の倍数だと分かる。この役割の分離が、答案の読みやすさを決める。

この形を作る計算が差である。f(n+1) から C・f(n) を引くと、f(n) の各項は消え、残るのは指数の進み方の差だけになる。二項の場合を式で書く。f(n) = A・uⁿ + B・vⁿ（A, B, u, v は整数で、u, v は正）とすると、次のようになる。

f(n+1) = A・uⁿ⁺¹ + B・vⁿ⁺¹ = u・A・uⁿ + v・B・vⁿ
u・f(n) = u・A・uⁿ + u・B・vⁿ
f(n+1) - u・f(n) = (v - u)・B・vⁿ

右辺に残ったのは、倍率の差 (v − u) と、第二項の係数と、第二項そのものである。だから、m が (v − u)・B を割り切れば、残りはいつでも m の倍数になる。あとは起点だけ確かめればよい。まとめると、次の条件がそろえば証明が閉じる。f(n) = A・uⁿ + B・vⁿ で、m が B(v − u) を割り切り、m が f(1) を割り切るなら、すべての正の整数 n で m は f(n) を割り切る。条件は二つだけで、どちらも代入で確かめられる。この形に入らない項が増えたときは、基準の倍率をどれにするかを選び直す。

指数の式は、n を1増やすと各項が決まった倍率で大きくなる。この性質は、余りの周期が使えない場面でも変わらない。12 と 3 のように互いに素でない組合せでは、3 の r 乗が 1 と合同になる r は存在しない。それでも 3 の余りは 3, 9, 3, 9 と繰り返すので、余りを並べれば先へ進める。差を作る方法と余りの周期を並べる方法は、どちらも指数が1進むと倍率が掛かるという同じ性質を見ている。片方が正しければ、もう片方も正しい。違うのは、答案に残る行の数と、条件をどこで確かめたかである。

向き不向きは、答案に残す行の数で決まる。差を作る方法は、項が3つ以上あるとき、法が大きいとき、指数の増分が項ごとに違うときに強い。計算の各段が等式で残るので、係数の選び方も答案で説明できる。余りの周期を並べる方法は、法が小さく、余りの周期が1行か2行で書けるときに強い。指数の形がそろっていて、余りの表を一度書けば終わる問題では、こちらが短い。

同じ問題でも、両方の答案が正しいことが多い。答案を書くときは、短く閉じる方法を選び、条件を確かめた行だけは残す。どちらの方法でも、確かめていない行を飛ばして結論を書くと、根拠のない答案になる。図1は、条件ごとにどちらの方法が向くかを並べたものである。

図1のように、項の数と法の大きさで方法の向きが変わる。法が小さく周期が短い問題では、余りの表を書く方が速い。項が増えて表が長くなる問題では、差を作る計算の方が短く閉じる。

よくある誤解を三つ挙げる。一つ目は、結論を仮定に混ぜること。二つ目は、指数の分け方を足し算と取り違えること。4 の 2n+3 乗は 4 の 2n+1 乗の 16 倍であって、4 の 2n+1 乗に 4 の 2 乗を足した数ではない。三つ目は、合同式の両辺を法と互いに素でない数で割ること。12 ≡ 0 (mod 12) の両辺を 3 で割って 4 ≡ 0 とするのは誤りである。割れるのは、法と互いに素な数だけである。この三つは、いずれも答案の一行目か二行目で起こる。式の計算を始める前に、仮定に何を置いたかを読み返すだけで防げる。

基本例題で差の作り方を確かめる

例題1（標準）　すべての正の整数 n について、13 は 4 の 2n+1 乗と 3 の n+2 乗の和を割り切ることを示しなさい。

f(n) = 4²ⁿ⁺¹ + 3ⁿ⁺² と置く。n が1増えると、4 の指数は2増えて 16 倍、3 の指数は1増えて 3 倍になる。基準の倍率を 16 に決めて、f(n+1) から 16f(n) を引く。式変形は次のとおりである。

f(n+1) = 4²ⁿ⁺³ + 3ⁿ⁺³
       = 16・4²ⁿ⁺¹ + 3・3ⁿ⁺²
16f(n) = 16・4²ⁿ⁺¹ + 16・3ⁿ⁺²
f(n+1) - 16f(n) = (3 - 16)・3ⁿ⁺² = -13・3ⁿ⁺²

よって f(n+1) = 16f(n) − 13・3ⁿ⁺² である。右辺の第二項は 13 の倍数だから、この等式は f(n+1) を f(n) の定数倍と法の倍数に分けた形になっている。答案は次の四段で書く。

第一に、n = 1 のとき f(1) = 4³ + 3³ = 64 + 27 = 91 = 13・7。よって 13 は f(1) を割り切る。第二に、n で 13 が f(n) を割り切ると仮定し、f(n) = 13k（k は整数）と置く。第三に、上の等式へ代入すると f(n+1) = 16・13k − 13・3ⁿ⁺² = 13(16k − 3ⁿ⁺²) となる。16k − 3ⁿ⁺² は整数だから、13 は f(n+1) を割り切る。第四に、以上より、すべての正の整数 n で 13 は f(n) を割り切る。

計算の確かめを二つ置く。n = 2 では 4⁵ + 3⁴ = 1024 + 81 = 1105 = 13・85、n = 3 では 4⁷ + 3⁵ = 16384 + 243 = 16627 = 13・1279 となり、答案の結論と一致する。引き算の符号は、n = 1 で f(2) − 16f(1) = 1105 − 1456 = -351 を計算し、右辺の -13・3³ = -351 と比べると確かめられる。符号を落とすと、最後のくくり出しで 13(16k + 3ⁿ⁺²) と書き、仮定の部分だけが残って見えなくなる。

この例題は、余りの周期を並べる方法でも三行で閉じる。4² = 16 = 13 + 3 なので 4² ≡ 3 (mod 13) である。すると 4²ⁿ⁺¹ = 4・(4²)ⁿ ≡ 4・3ⁿ、3ⁿ⁺² = 9・3ⁿ だから、和は 4・3ⁿ + 9・3ⁿ = 13・3ⁿ ≡ 0 (mod 13) となる。短い関係が見つかる問題では、こちらの方が速い。

差を作る答案が生きるのは、短い関係が見つからないとき、または項が増えて余りの表が長くなるときである。図2のように、仮定から結論までの道筋を一本につなぐと、どの行で仮定を使ったかが見える。答案では、どちらの方法を選んだかを一行目に書き、条件を確かめた行を残す。

図2の流れでは、仮定の f(n) を 16 倍したものから、法の倍数を引いて f(n+1) に着く。仮定を使ったのは 16 倍の部分だけで、引いた部分は 13 の倍数として処理している。

係数が法を吸収する場合と、項が増える場合

例題2（やや難）　すべての正の整数 n について、12 は 2・3ⁿ + 6・5ⁿ を割り切ることを示しなさい。

f(n) = 2・3ⁿ + 6・5ⁿ と置く。倍率は 3 と 5 で、その差は 2 である。2 は 12 を割り切らない。それでも、5 の項の係数 6 を掛けると 6・2 = 12 になり、法で割り切れる。この場合は、係数が法を吸収している。差を計算すると次のようになる。

f(n+1) = 2・3ⁿ⁺¹ + 6・5ⁿ⁺¹
       = 3・(2・3ⁿ) + 5・(6・5ⁿ)
3f(n) = 3・(2・3ⁿ) + 3・(6・5ⁿ)
f(n+1) - 3f(n) = (5 - 3)・6・5ⁿ = 12・5ⁿ

よって f(n+1) = 3f(n) + 12・5ⁿ である。起点は n = 1 で f(1) = 6 + 30 = 36 = 12・3。仮定を f(n) = 12k と置くと、f(n+1) = 3・12k + 12・5ⁿ = 12(3k + 5ⁿ) となり、13 の例と同じ形で閉じる。

この例題には、開始番号の注意が付く。n = 0 を入れると f(0) = 2 + 6 = 8 で、12 では割り切れない。問題文が正の整数と断っているのはこのためである。差の形は n = 0 でも同じように作れるが、起点の確認で落ちる。開始番号を広げて示したいときは、最初に成り立つ n を代入で探し、そこを起点に書き直す。

余りの周期を並べる方法でも同じ結論になる。3 と 12 は互いに素ではないので、3 の r 乗が 1 と合同になる r は存在しない。それでも 3ⁿ の余りは 3, 9 を、5ⁿ の余りは 5, 1 を繰り返す。n が奇数のときは 2・3 + 6・5 = 36 ≡ 0、偶数のときは 2・9 + 6・1 = 24 ≡ 0 で、どちらも 12 の倍数である。場合分けが2行で済むなら余りの表が短い。ただし、余りが 1 に戻らない底が混ざると、表の作り方で迷いやすい。

例題3（難）　すべての正の整数 n について、27 は 5 の n+2 乗と 2 の 5n+1 乗の和を割り切ることを示しなさい。

f(n) = 5ⁿ⁺² + 2⁵ⁿ⁺¹ と置く。倍率は 5 と 32 である。32 − 5 = 27 なので、基準の倍率を 5 にすると、差の係数がそのまま法になる。計算は次のとおりである。

f(n+1) = 5ⁿ⁺³ + 2⁵ⁿ⁺⁶
       = 5・5ⁿ⁺² + 32・2⁵ⁿ⁺¹
5f(n) = 5・5ⁿ⁺² + 5・2⁵ⁿ⁺¹
f(n+1) - 5f(n) = (32 - 5)・2⁵ⁿ⁺¹ = 27・2⁵ⁿ⁺¹

起点は n = 1 で f(1) = 5³ + 2⁶ = 125 + 64 = 189 = 27・7。仮定を f(n) = 27k と置くと、f(n+1) = 5・27k + 27・2⁵ⁿ⁺¹ = 27(5k + 2⁵ⁿ⁺¹) となる。n = 2 では 5⁴ + 2¹¹ = 625 + 2048 = 2673 = 27・99、n = 3 では 5⁵ + 2¹⁶ = 3125 + 65536 = 68661 = 27・2543 で、いずれも結論と一致する。

この例題で余りの周期を並べると、表が長くなる。2 と 27 は互いに素なので、2 の r 乗が 1 と合同になる r は存在し、その最小の r は 18 である。指数 5n+1 を 18 で割った余りは n とともに動き、余りの表は 18 行になる。5 の側にも同じ長さの周期があるので、表だけで答案の大半が埋まる。差を作る答案は、32 = 27 + 5 という一行の事実だけで閉じる。

余りの周期を並べる方法が短くなるのは、2⁵ = 32 ≡ 5 (mod 27) という小さい関係に気づいたときである。気づけば 2⁵ⁿ⁺¹ = 2・(2⁵)ⁿ ≡ 2・5ⁿ、5ⁿ⁺² = 25・5ⁿ となり、和は 27・5ⁿ で割り切れる。差を作る計算は、この関係を 32 − 5 = 27 という引き算の形で先に見せてくれる。同じ事実を、どちらの入口から取り出すかの違いである。

項が3つ以上になると、基準の倍率を一つ選んだだけでは残りが法の倍数にならないことがある。そのときは、残った項の係数が法を吸収するか、もう一つの倍率の差が法の倍数になるかを確かめる。どちらも成り立たなければ、その問題は差を作る形では閉じない。法を素因数に分けて、それぞれで示す道を選ぶ。分けた先で別の差を作ることもある。基準を選び直す判断は、差を計算して残った係数を見てから行う。先に決めてから計算すると、合わないときに式全体を書き直すことになる。

誤答の実例と直し方

最初の誤答は、n+1 の場合も成り立つと仮定して、その仮定から n+1 の場合を導くものである。答案には「n+1 のときも 13 で割り切れると仮定すると」と書かれ、そのあとに結論が続く。原因は、帰納法の仮定が P(n) だけであることを見落とした点にある。直し方は、仮定を f(n) = 13k の形に固定し、f(n+1) は差の等式で計算することである。図3の上段が誤りの道、下段が正しい道にあたる。

二つ目の誤答は、指数の分け方を足し算と取り違えるものである。4 の 2n+3 乗を 4 の 2n+1 乗と 4 の 2 乗の和として扱うと、差を引いても残りが法の倍数にならず、計算が合わなくなる。指数法則は掛け算で働く。4²ⁿ⁺³ = 4²・4²ⁿ⁺¹ = 16・4²ⁿ⁺¹ と直す。原因は、指数の足し算と底の掛け算の区別が曖昧なまま計算を進めたことにある。直し方は、n を1増やすたびに掛かる数を先に書き出すことである。

三つ目の誤答は、差の等式の途中で法の倍数を落とすものである。f(n+1) − 16f(n) = -13・3ⁿ⁺² の右辺を「13 の倍数だから 0」と書いて f(n+1) = 16f(n) としてしまう。13 の倍数であることは、等式の右辺から消せることを意味しない。消えるのは、合同式で 0 と合同だと言えるときだけである。直し方は、等式のまま残し、最後に 13 でくくることである。くくったあとの (16k − 3ⁿ⁺²) が整数だと一言添えれば、答案は閉じる。

三つの誤答に共通する原因は、答案の一行目で仮定の形を決めていないことである。書き始める前に f(n) = mk と置き、n+1 の式をその形へ近づける計算を先に済ませておくと、誤りの大半は入り込む余地を失う。

練習問題

問1（標準）　すべての正の整数 n について、3 は 4ⁿ + 5 を割り切ることを示しなさい。

問2（標準）　すべての正の整数 n について、7 は 2³ⁿ + 6 を割り切ることを示しなさい。

問3（標準）　すべての正の整数 n について、9 は 6・4ⁿ + 3・7ⁿ を割り切ることを示しなさい。

問4（やや難）　すべての正の整数 n について、11 は 3³ⁿ + 2・5ⁿ⁺¹ を割り切ることを示しなさい。

問5（やや難）　すべての正の整数 n について、8 は 2・5ⁿ + 2・9ⁿ + 4 を割り切ることを示しなさい。

問1の答え

f(n) = 4ⁿ + 5 と置く。f(n+1) = 4ⁿ⁺¹ + 5 = 4(4ⁿ + 5) − 15 = 4f(n) − 15。起点は f(1) = 9 = 3・3。仮定を f(n) = 3k と置くと、f(n+1) = 12k − 15 = 3(4k − 5) で、4k − 5 は整数である。よって 3 はすべての正の整数 n で f(n) を割り切る。n = 2 では 16 + 5 = 21 = 3・7 となり、結論と一致する。定数項があるときは、n を1増やしたときの定数項の差も一緒に引くのがこつである。

問2の答え

f(n) = 2³ⁿ + 6 = 8ⁿ + 6 と置く。f(n+1) = 8ⁿ⁺¹ + 6 = 8(8ⁿ + 6) − 42 = 8f(n) − 42。起点は f(1) = 8 + 6 = 14 = 7・2。仮定を f(n) = 7k と置くと、f(n+1) = 56k − 42 = 7(8k − 6) である。よって 7 はすべての正の整数 n で f(n) を割り切る。n = 2 では 64 + 6 = 70 = 7・10 となり、結論と一致する。指数の増分が3なので、倍率は 2 の 3 乗で 8 になる。

問3の答え

f(n) = 6・4ⁿ + 3・7ⁿ と置く。f(n+1) = 24・4ⁿ + 21・7ⁿ = 4(6・4ⁿ + 3・7ⁿ) + 9・7ⁿ = 4f(n) + 9・7ⁿ。起点は f(1) = 24 + 21 = 45 = 9・5。仮定を f(n) = 9k と置くと、f(n+1) = 36k + 9・7ⁿ = 9(4k + 7ⁿ) である。よって 9 はすべての正の整数 n で f(n) を割り切る。n = 2 では 96 + 147 = 243 = 9・27 となり、結論と一致する。倍率の差は 3 で 9 を割り切らないが、係数 3 を掛けると 9 になる。例題2と同じく、係数が法を吸収している。

問4の答え

f(n) = 3³ⁿ + 2・5ⁿ⁺¹ = 27ⁿ + 10・5ⁿ と置く。f(n+1) = 27ⁿ⁺¹ + 10・5ⁿ⁺¹ = 27f(n) + 10・5ⁿ(5 − 27) = 27f(n) − 220・5ⁿ。220 = 11・20 なので、残った項は 11 の倍数である。起点は f(1) = 27 + 50 = 77 = 11・7。仮定を f(n) = 11k と置くと、f(n+1) = 297k − 220・5ⁿ = 11(27k − 20・5ⁿ) である。よって 11 はすべての正の整数 n で f(n) を割り切る。n = 2 では 729 + 250 = 979 = 11・89 となり、結論と一致する。差が法の倍数になるかは、係数を含めて確かめる。

問5の答え

f(n) = 2・5ⁿ + 2・9ⁿ + 4 と置く。f(n+1) = 10・5ⁿ + 18・9ⁿ + 4 = 5(2・5ⁿ + 2・9ⁿ + 4) + 8・9ⁿ − 16 = 5f(n) + 8(9ⁿ − 2)。残った項は 8 の倍数である。起点は f(1) = 10 + 18 + 4 = 32 = 8・4。仮定を f(n) = 8k と置くと、f(n+1) = 40k + 8(9ⁿ − 2) = 8(5k + 9ⁿ − 2) である。よって 8 はすべての正の整数 n で f(n) を割り切る。n = 2 では 50 + 162 + 4 = 216 = 8・27 となり、結論と一致する。項が3つあっても、基準の倍率を一つ決めて引けば、残りは一つの式にまとまる。

覚えておくこと

• 帰納法の仮定は f(n) についてだけ置き、f(n+1) は結論として扱う。
• f(n+1) を C・f(n) + m・G(n) の形に直す。C は指数の進み方から決まる倍率である。
• 差を引いて残った係数が法の倍数になるかを、係数を含めて確かめる。
• 起点の n を式に入れて、法で割り切れるかを計算する。
• 余りの周期が短く書けるときは、そちらの答案も比べて短い方を選ぶ。

つまずきの見分け方

答案が止まったら、まず仮定に置いた式を探す。f(n) = mk の形になっていなければ、結論を仮定に混ぜている。次に、f(n+1) の式の各項が、n の式の何倍になっているかを書き出す。倍率が書けていれば、差を作る計算は一通りに決まる。最後に、残った係数と法の関係を見る。係数が法を吸収している場合と、倍率の差が法の倍数になる場合の二つを、順に確かめる。計算の確かめは、起点と、その次の n の二つを代入して行う。二つが合えば、差の等式の符号の誤りはほぼ見つかる。指数が進んでも、法から見れば残るのは倍率の差だけです。答案の最初に置くのは、その差を等式で書いた一行です。