ドミノ倒し
数学的帰納法を理解するために，ドミノ倒しの例を考える．
ドミノ倒しという遊びがある．ドミノを床に立ち並べ，並べ終えたら最初の1枚を倒す．すると，その勢いで後に続くドミノが次々と倒れていき，最終的には全てのドミノを倒すことができる．逆に，ドミノがうまく倒れず途中で止まってしまうこともある．
ドミノ倒しを成功させる要領はなんだろうか．それは
- 最初の1 枚をしっかりと立てる
- 2枚目以降のドミノを，直前の1枚が倒れた勢いで倒れるように立てる
ことである．この2点さえ確実に守れば，ドミノ倒しの規模をどんどん大きくすることができる．1個，2個，3個， $\cdots$ とドミノの数を増やしていけば，理論的には無限個のドミノ倒し(もちろん現実には不可能だが)も成功するはずである．
これから学ぶ数学的帰納法では，このドミノ倒しと同じ要領で数学の証明をおこなう．
すなわち，数学的帰納法は
- まず出発点となる命題を証明する
- 直前の命題が正しければ次の命題も正しいことを証明する
ことで，全ての場合において正しさを証明しまおう，という手法である．
以下では，数式の例を用いて数学的帰納法を説明していく．