数学的帰納法

数学的帰納法とは、数学における証明方法の一種である。日本では高校レベルの数学の演習でしばしば用いられるテクニックの一つであり、大学受験で数学を利用するならぜひ身に着けておきたい方法である。

なお、初学者向けにこのやり方を説明する際には、しばしばドミノ倒しに例えられる。ドミノ倒しは正しい配置であれば1枚目が倒れれば2枚目も、3枚目も倒れる…といった具合であるが、「k枚目が倒れれば(k＋1)枚目が倒れる」という点で数学的帰納法に近いイメージを抱くことが出来るからである。

証明方法

「P(n)が成り立つ」という命題を証明したい。このとき、

• n=1のときP(n)が成り立つ
• n=kの時P(n)が成り立つとすると、n=k+1のときもP(n)が成り立つ。

これらの2点を示すことが出来れば上記の命題が成り立つことを証明できる。

練習問題 :

任意の正の整数 n に対して、 $1+2+3+\cdots +n={\frac {n(n+1)}{2}}$ となることを証明せよ。

解答と解説は右をクリックして表示！

(1) n = 1 のとき題意が成り立つことを示す。 (左辺) = 1 (右辺) = 1(1+1) / 2 = 1 よって n = 1 のときは成り立つ。 (2) n = k で題意が成り立つならば、 n = k + 1 のときも題意が成り立つことを示す。 $1+2+3+\cdots +k={\frac {k(k+1)}{2}}$ が成り立つと仮定する。 これを用いて n = k + 1 のとき式を変形すると、 ${\begin{aligned}1+2+3+\cdots +k+(k+1)&={\frac {k(k+1)}{2}}+(k+1)&={\frac {(k+1)(k+2)}{2}}\end{aligned}}$ よって n = k + 1 のときも成り立つ。 (1), (2) より、全ての正の整数 n に対して題意は成り立つ。

練習問題 :

任意の正の整数 n に対して、 $10^{n}-1$ は9の倍数であることを証明せよ。

解答と解説は右をクリックして表示！

(1) n = 1 のとき題意が成り立つことを示す。 10 - 1 = 9 は9の倍数である。 (2) n = k で題意が成り立つならば、 n = k + 1 のときも題意が成り立つことを示す。 $10^{k}-1$ が9の倍数だと仮定すると、 n = k + 1 のとき、 $10^{k+1}-1=10\times (10^{k}-1)+9$ ここで、 $10^{k}-1$ は9の倍数なので、 $10^{k+1}-1$ も9の倍数である。 (1), (2) より、全ての正の整数 n に対して $10^{n}-1$ は9の倍数である。

名称について

「帰納」とは、一般に、個々のケース(事例)から全体に適応可能な法則やルールを見つけ出していくことである。また、これに対して普遍的な法則やルールから個別具体的な状況に説明を与える方法を「演繹」という。数学的帰納法は、それこそ前述のドミノ倒しの例えのように、徐々に結論に近づいていく様子が帰納的に見えることから名付けられた。しかし、実際には演繹的な証明方法である。すなわち、「P(k)に対してP(k+1)が成り立つ」という普遍的な法則があらゆる自然数の場合を貫いているからである。

また、「P(n)とP(n+1)が成り立っていればP(n+2)が成り立つ」というものを用いた数学的帰納法は、とくに一昨日帰納法と呼ばれる。これは「帰納」と「昨日」をかけた洒落である。一昨日帰納法を用いる場合、最初に倒すドミノが2つ必要な点に注意。詳しくは別途リンク先の記事をご覧いただきたい。

派生形式

自然数・正の整数に限らず、「すべての整数」について成り立つことを数学的帰納法で証明したい場合は、以下の手順となる。ただし、この手の問題はなかなか出ない。

• n=1のときP(n)が成り立つ(n=0でも良い)
• n=kの時P(n)が成り立つとすると、n=k+1のときおよびn=k-1のときもP(n)が成り立つ。

また、全ての実数について成り立つことを証明するのには適用できない。

適用例

ハゲの証明

• 髪の毛が0本の人はハゲである。
• 髪の毛がk本の人がハゲならば、k+1本の人もハゲである。

この二つの前提に対して、帰納法を適用することによって全人類がハゲであることが導かれる。 (真面目な話、ハゲであるか否かは、真偽・01・TorFの二値的なものではなく、グラデーション的なものであるだろう。そのため、「髪の毛がn本の人がハゲならば、n+1本の人もハゲである。」は必ずしも成り立たない。)