数学的帰納法は、自然数 n についての命題を、「最初の1個が成り立つ」ことと、「ある段階で成り立つなら次でも成り立つ」ことの二段階で証明する方法です。ドミノの例は有名ですが、本質は「次へ渡せる仕組み」を証明することにあります。
証明は二つの部品に分かれる
数学的帰納法の基本形は次の二つです。
- n=1 のとき命題が成り立つことを示す。
- n=k のとき成り立つと仮定し、その仮定から n=k+1 でも成り立つことを示す。
この二つがそろうと、1で成り立つことが2へ、2で成り立つことが3へ、と順に受け渡されます。だからすべての自然数へ広がります。
重要なのは、2で「n=k のとき正しい」と証明し直すのではなく、仮定を使って次の段階へ渡すことです。
例：1+2+…+n の公式を証明する
命題
を証明します。
まず n=1 では、左辺は1、右辺も 1×2/2=1 なので成り立ちます。
次に n=k で
が成り立つと仮定します。すると n=k+1 の左辺は
です。仮定を使うと
=(k+1)(k+2)2
となり、これは公式に n=k+1 を入れた形です。よって次へ渡せました。
仮定は『証明したことにする』ズルではない
「n=k のとき成り立つと仮定していいなら、最初から全部正しいと仮定しているのでは？」と疑問に感じることがあります。
しかし仮定しているのは、すべてのnで正しいことではありません。「もしあるkで正しいなら、次のk+1でも正しくなる」という条件を証明するため、一時的に一段だけ置いています。
そのうえで最初の n=1 が本当に成り立つことを別に確認するので、連鎖を始める場所も保証されます。
つまずきやすいのは k+1 側の形を先に決めないこと
帰納法の式変形で迷ったら、まず「k+1 のとき最終的にどの形になればよいか」を書きます。
先ほどの公式なら目標は
です。
左辺へ k+1 を追加し、帰納法の仮定で前半を置き換え、目標形へ因数分解します。ゴールを見ずに式を展開し続けると、どこへ向かっているか分からなくなります。
初項を確認し忘れると連鎖は始まらない
帰納法で2段目だけを証明しても、「成り立つところが一つでもあれば次も成り立つ」と言えただけです。最初に実際に成り立つ点がなければ、全体の証明にはなりません。
また、命題が n≥ 3 から始まるなら、確認すべき最初は n=3 です。いつも n=1 と機械的に書くのではなく、命題の範囲を見ます。
「開始点」と「受け渡し」の二つを答案上でも明確に分けると、論理の抜けを防げます。
帰納法が向かない問題もある
すべての自然数命題を帰納法で証明すべきではありません。直接式変形した方が短い恒等式や、図形の性質を別の定理から一度に示せる問題もあります。
帰納法が特に自然なのは、nからn+1への構造が見える問題です。数列の和、漸化式、整除性、不等式などで「一段増えたとき何が追加されるか」を表しやすい場合に力を発揮します。
次は『仮定をどこで使ったか』へ線を引く
帰納法の答案を見直すときは、帰納法の仮定を使った行へ線を引いてください。線が一本も引けないなら、仮定を使わず式変形しているだけかもしれません。
次に、開始点の確認と、k+1での目標形を四角で囲みます。問題が変わっても、開始点→仮定→次の段階→目標形という骨組みは同じです。
不等式の帰納法では『仮定を強く使う』
たとえば自然数nについてある不等式を証明するとき、n=k+1 の式へ変形する途中で、帰納法の仮定をそのまま代入するだけでなく、両辺へ正の数を足す、正の数を掛けるなど不等号を保つ操作を使います。
ここで注意するのは、負の数を掛けると不等号の向きが反転することです。等式の帰納法と同じ感覚で機械的に変形すると論理が崩れます。帰納法は一つの型ですが、中で使う代数・不等式の規則は別に正しく扱う必要があります。
「n=kで正しい」から「n=k+1でも正しい」へ何を運ぶのか
帰納法で最も大切なのは、仮定を書いたあとに放置しないことです。たとえば
1+2+·s+n=n(n+1)/2
を証明するとき、n=kで
1+2+·s+k=k(k+1)/2
と仮定したら、k+1の場合の左辺を
1+2+·s+k+(k+1)
と書きます。ここで前半を仮定に置き換え、
k(k+1)/2+(k+1)
から
(k+1)(k+2)/2
へ変形できれば、k+1の場合の形へ届きます。
「仮定した式」と「示したい式」を別々に眺めるのではなく、k+1側の途中にkの場合を見つけて差し替えるのが操作の中心です。
練習：どこで仮定を使うかだけ先に探す
1+3+5+·s+(2n-1)=n2
を帰納法で考えます。n=kで左辺がk²になると仮定し、次の奇数2k+1を足すと、
k2+2k+1=(k+1)2
です。計算自体は短くても、「次の一項を足すとk+1の目標形になる」という橋が見えています。
帰納法の問題では、式変形の前に「kの場合の仮定を、k+1の場合のどこへ代入できるか」を探してください。
