数学的帰納法
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる:
1枚目のドミノが倒れることを示す。
任意の自然数 k に対して、「k 枚目のドミノが倒れるならば k + 1 枚目のドミノが倒れる」ことを示す。
以上の議論から全てのドミノが倒れることが結論づけられる。
数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より
(a) P(1)
が正しいことが分かる。次に k = 1, 2, ... に対して 2 を適用することで、
(b) P(1) ⇒ P(2),
(c) P(2) ⇒ P(3),
...
が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせることにより P(3) が従う。以下同様に P(4), P(5), ... も従い、結局3の
全ての自然数 n に対し P(n) が成り立つ
が結論づけられる。
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
数学的帰納法(すうがくてききのうほう、英: mathematical induction)は、数学における証明の手法の一つである。
例えば自然数に関する命題 P(n) が全ての自然数 n に対して成り立つことを証明するために、次のような手続きを行う。
P(1) が成り立つことを示す。
任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つことを示す。
1と2の議論から任意の自然数 n について P(n) が成り立つことを結論づける。