数学的帰納法の原理

ドミノ倒し

数学的帰納法を理解するために,ドミノ倒しの例を考える.

ドミノ倒しという遊びがある.ドミノを床に立ち並べ,並べ終えたら最初の1枚を倒す.すると,その勢いで後に続くドミノが次々と倒れていき,最終的には全てのドミノを倒すことができる.逆に,ドミノがうまく倒れず途中で止まってしまうこともある.

ドミノ倒しを成功させる要領はなんだろうか.それは

  1. 最初の1 枚をしっかりと立てる
  2. 2枚目以降のドミノを,直前の1枚が倒れた勢いで倒れるように立てる

ことである.この2点さえ確実に守れば,ドミノ倒しの規模をどんどん大きくすることができる.1個,2個,3個, $\cdots$ とドミノの数を増やしていけば,理論的には無限個のドミノ倒し(もちろん現実には不可能だが)も成功するはずである.

これから学ぶ数学的帰納法では,このドミノ倒しと同じ要領で数学の証明をおこなう.

すなわち,数学的帰納法は

  1. まず出発点となる命題を証明する
  2. 直前の命題が正しければ次の命題も正しいことを証明する

ことで,全ての場合において正しさを証明しまおう,という手法である.

以下では,数式の例を用いて数学的帰納法を説明していく.

数学的帰納法の例

次の問題を考えてみよう.

数学的帰納法の例

すべての自然数 $n$ において

\[\sum_{k=1}^nk(k+1)=\frac{1}{3}n(n+1)(n+2)\tag{1}\label{kinohonorei}\]

を証明せよ

本当にこの $\eqref{kinohonorei}$ が成立するかどうか,試しに $n=1$ を代入してみると

\begin{align} (左辺)&=\sum_{k=1}^1k(k+1)=1\cdot2=2\\ (右辺)&=\frac{1}{3}\cdot1\cdot2\cdot3=2 \end{align}

となり成立している.

次に, $n=2$ の場合も

\begin{align} (左辺)&=\sum_{k=1}^2k(k+1)=1\cdot2+2\cdot3=8\\ (右辺)&=\frac{1}{3}\cdot2\cdot3\cdot4=8 \end{align}

で成立している.

また, $n=3$ の場合も

\begin{align} (左辺)&=\sum_{k=1}^3k(k+1)=1\cdot2+2\cdot3+3\cdot4\\ &=20\\ (右辺)&=\frac{1}{3}\cdot3\cdot4\cdot5=20 \end{align}

で確かに成立している.

しかし, $n$ が $1,2,3$ の場合に成立したからといって, $\eqref{kinohonorei}$ が全ての自然数で成立するかはまだわからない.なぜなら, $n=4$ 以上の場合の成立についてはまだ確かめていないからである.

かといって,4以上の $n$ について1つずつ調べていったとしても,無限にある自然数を調べ尽くすことはできない.

ここで威力を発揮するのが数学的帰納法(mathematical induction)である.

ある自然数 $m$ の場合に $\eqref{kinohonorei}$ が成り立つと仮定したとき,その次の自然数 $m+1$ の場合にも $\eqref{kinohonorei}$ が成り立つ.

ことを証明しよう.

これさえ証明してしまえば, $n=1$ の場合には $\eqref{kinohonorei}$ が成り立つことがすでに証明されているので,その次の $n=2$ の場合も成り立つ.

$\bigcirc$ は成立が示されたもの.●は成立がまだ示されていないものとして並べると,次のようになる.

また, $n=2$ の場合が成り立つならば,同様にしてその次の $n=3$ の場合も成り立つ.

以降,冒頭のドミノ倒しの例のように,次々と $\eqref{kinohonorei}$ が成り立つことが示される.この論法に終わりはないので,すべての自然数 $n$ に対して $\eqref{kinohonorei}$ が成り立つと結論付けてよい.