数学的帰納法の原理

ドミノ倒し

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

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

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

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

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

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

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

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

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

すべての自然数 $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}$ が成り立つと結論付けてよい．