数学的帰納法の例
次の問題を考えてみよう．
数学的帰納法の例
すべての自然数 $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}$ が成り立つと結論付けてよい．