最終更新:2019/04/29

数学的帰納法のパターンまとめ

分野: まとめ

数学的帰納法とは「全ての自然数 $n$ に対して○○が成り立つことを証明せよ」というタイプの問題に有効な証明方法です。

この記事では,数学的帰納法について基礎から分かりやすく解説します。また,数学的帰納法のいろいろな応用パターンや難しい例題も紹介します。

数学的帰納法とは

数学的帰納法は「全ての自然数 $n$ に対して○○が成り立つことを証明せよ」という問題に有効な方法です。

実は,以下のAとBが分かれば,証明は完了したことになります!
A. $n=1$ のとき○○は成り立つ
B. $n=k$ のとき○○が成立すると仮定すると,$n=k+1$ のときも○○は成り立つ

なぜなら,AとBが証明できれば,
・$n=1$ の場合はAより○○が成立
・さらに,Bを $k=1$ として使うと $n=2$ でも○○が成立
・さらに,Bを $k=2$ として使うと $n=3$ でも○○が成立
・さらに…

のように,いくらでも続けられるので,全ての自然数 $n$ に対して○○が成り立つことが分かります。

以上が,数学的帰納法を使った証明方法の流れです。ここからは,具体例を通じて数学的帰納法を理解していきましょう。

数学的帰納法の最も簡単な例

全ての自然数 $n$ に対して,$1$ から $n$ までの足し算が $\dfrac{1}{2}n(n+1)$ と等しいことを,数学的帰納法を使って証明してみましょう。つまり,証明すべき等式は
$1+2+\dots +n=\dfrac{1}{2}n(n+1)$
です。

数学的帰納法で証明するためには,以下のAとBの2つを証明する必要があります。

「A. $n=1$ のとき○○は成り立つ」の証明

・$n=1$ のとき
$1=\dfrac{1}{2}\times 1\times 2$
なので,目標の等式が成立します。

「B. $n=k$ のとき○○が成立すると仮定すると,$n=k+1$ のときも○○は成り立つ」の証明

・$n=k$ のとき目標の等式が正しいと仮定すると
$1+2+\dots +k=\dfrac{1}{2}k(k+1)$
となります。両辺に $(k+1)$ を加えると,
$1+2+\dots +k+(k+1)\\
=\dfrac{1}{2}k(k+1)+(k+1)$
となります。右辺を変形すると,
$\dfrac{1}{2}(k+1)(k+2)\\
=\dfrac{1}{2}(k+1)\{(k+1)+1\}$
となります。つまり,$n=k+1$ のときにも目標の等式が正しいです。

よって,数学的帰納法により,全ての自然数 $n$ に対して目標の等式が正しいことが証明されました。

1:数学的帰納法の基本パターン

数学的帰納法の基本パターンは
A. $n=1$ のとき○○は成り立つ
B. $n=k$ のとき○○が成立すると仮定すると,$n=k+1$ のときも○○は成り立つ

の2つを証明することでした。

この基本パターンで証明できる主張はたくさんあります(難しいものも多いです)。

定理1:
全ての自然数 $n$ について,連続する $n$ 個の整数の積は $n!$ の倍数である

定理1の数学的帰納法による証明は連続するn個の整数の積と二項係数の3番目の証明です。

他にも,数学的帰納法の基本パターンは
包除原理の2通りの証明の2番目の証明
イェンゼンの不等式の3通りの証明の1番目の証明
ライプニッツの公式の証明と二項定理
などに登場します。

2:一つ前だけでなく二つ前も仮定するパターン

ここからは,数学的帰納法の応用パターンです。

$n=1, 2$ の場合を証明した後,$n=k,k+1$ の場合を仮定して,$n=k+2$ の場合にも成り立つことを証明するパターンです。

例えば,$1,1,2,3,5,8,13,\dots$ のように続く有名な数列「フィボナッチ数列」の一般項が
$\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$
となることを証明できます。

詳細は,フィボナッチ数列の一般項と数学的帰納法の中盤,「ビネの公式の証明」の2つめで解説しています。

さらに,3つ以上仮定することもあります。

3:前の項を全て仮定するパターン

先ほどのパターン2をさらに一般化したもので,数学オリンピックの離散数学などの難問ではこのパターンが多いです。 $n=1$ の場合を証明した後,$n\leq k-1$ を満たす全ての自然数 $n$ に対して成り立つと仮定して,$n=k$ の場合にも成り立つことを証明します。

4:後ろ向き帰納法(無限降下法)

$n=k$ のときを仮定して $n=k-1$ の場合を証明します。背理法と組み合わせて使うことが多く,無限降下法と呼ばれます。

5:多変数の数学的帰納法

レアなケースです。複数の自然数のペア $(m, n)$ 全てに関して成立すること示します。原点から離れる方向にドミノ倒しをしていくイメージです。

以上の5パターンを把握しておけば,数学的帰納法の応用の幅が広がります!

数学的帰納法は素晴らしい

数学的帰納法は整数問題,数列,組み合わせ(離散数学),恒等式の証明,などなど様々な分野の証明問題に使える非常に強力な方法です。自然数 $n$ が登場する証明問題の多くは数学的帰納法で解決できます。

数学的帰納法を用いた証明と,数学的帰納法を用いずに直接証明する方法を比べると,一般的に以下のような特徴が見受けられます:

数学的帰納法:機械的な計算で証明できることが多い,発想力がいらない
直接証明する方法:発想力が必要な場合が多い,よりエレガントな解答になりやすい

もちろん,数学オリンピックの問題など,数学的帰納法を用いた上でも発想力が必要になる問題もありますが,自然数 $n$ が含まれる証明問題を見たらとりあえず,どの分野でも数学的帰納法を連想しましょう。

数学的帰納法を使えば全ての人がハゲであることを証明できます→数学的帰納法によるハゲのパラドックス