数学的帰納法（すうがくてききのうほう、）は自然数に関する命題"P"("n") が全ての"n" に対して成り立っている事を証明するための、次のような証明手法である。上で1.と2.から3.を結論づける所が数学的帰納法に当たる。自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2. により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。"P"("n")を「"n"枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる：数学的帰納法が成り立つ直観的理由は以下の通りである。まず1.よりが正しい事が分かる。次に "k" = 1, 2, ...に対して2. を適用する事で、が分かる。(a), (b)より、"P"(2) が成り立ち、この事実と(c)を組み合わせる事により"P"(3)が従う。以下同様に "P"(5), "P"(6), …も従い、結局3.のが結論づけられる。ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1., 2. と 3. の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。変数変換によって明らかなように、変数"n"が表す範囲は"n" → "n" + 1という操作で閉じていれば {1, 2, ... } である必要はなく、0を自然数に含めることにしたり、あるいは任意の整数 "m" に関する {"m

出典:wikipedia