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

数学的帰納法とは

数学的帰納法は「全ての自然数 $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つを証明する必要があります。

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

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

A. $n=1$ のとき○○は成り立つ

B. $n=k$ のとき○○が成立すると仮定すると，$n=k+1$ のときも○○は成り立つ

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

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

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

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

→高校数学の問題集　～最短で得点力を上げるために～のT145でも有名問題と4通りの解答を紹介しています。

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\}$

となることを証明できます。

詳細は，フィボナッチ数列の7つの性質（一般項・黄金比・互いに素）の中盤，「ビネの公式の証明」の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$ が含まれる証明問題を見たらとりあえず，どの分野でも数学的帰納法を連想しましょう。