ハノイの塔問題・考察（２）を示します。
考察（２）：数学的帰納法とは
「正しい」か「正しくない」かのいずれかである文を命題という。たとえば、「日本の人口は、2012年現在１億人を越えている。」という文は、正しい命題である。「8は素数である。」という文は、正しくない命題である。また、「恐竜が絶滅したのは地球に巨大隕石が衝突したからである。」という文は、正しいか正しくないかわかっていないが、どちらかであるには違いない。したがって、命題といえる。ところが、「この花はなんと美しいのだろう！」とか「それはほんとうですか？」というような感嘆文や疑問文は命題とはいわない。
命題P(n)を考える。
命題P(n)について、nの値が1のとき、2のとき、3のとき、…と調べていき有限個の値で正しくても、すべての自然数について、命題が正しいとはいえない。まだ先の値で正しくないかもしれないからである。
ところが、nの値が1のとき、2のとき、3のとき、･･･とすべての自然数について調べ尽くすのは不可能である。命題P(n)のような、すべての自然数に対する命題の正しさを保証するのが、数学的帰納法である。
自然数nに関する命題P(n)に対して、つぎの(Ａ)と(Ｂ)を示すことができるとき、自然数1以上のすべての自然数nに対して命題P(n)は、正しいと結論できる。
（Ａ）自然数1において命題P(1)は正しい。
（Ｂ）1以上の任意の自然数kに対して、
自然数nの値がkのとき、命題P(k)が正しいならば、自然数nの値がk+1の
ときも命題P(k+1)が正しい。
(Ａ)と(Ｂ)が示されたとき、命題P(n)の正しさはつぎのように考えるとわかりやすい。
まず、(Ａ)が示されているので、自然数nの値が1のとき命題P(1)の正しさがわかる。つぎに、(Ｂ)が示されているので、2のときの命題P(2)の正しさがわかる。 2のときの命題P(2)の正しさがわかったので、再び(Ｂ)を適用すると3のときの命題P(3)の正しさがわかる。あとは、連鎖的に正しさが示されていく。
P(1) →P(2)→P(3)→P(4)→･･･→P(k)→P(k+1)→･･･
数学的帰納法は、自然数に関する等式や不等式の命題の証明にはもちろん、ある手順が可能かどうかを証明するときにも有用である。
