数学的帰納法
数学的帰納法（すうがくてききのうほう、）は自然数に関する命題 が全ての自然数 に対して成り立っている事を証明するための、次のような証明手法である。
上で1と2から3を結論づける所が数学的帰納法に当たる。自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。
なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた。
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。 を「 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる：
数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より
が正しい事が分かる。次に に対して 2 を適用する事で、
が分かる。(a), (b) より、 が成り立ち、この事実と (c) を組み合わせる事により が従う。以下同様に , , …も従い、結局 3 の
が結論づけられる。
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
変数変換によって明らかなように、変数 が表す範囲は という操作で閉じていれば である必要はなく、 を自然数に含めることにしたり、あるいは任意の整数 に関する という範囲でもよいことになる。
例えば ではなく、 で証明し、開始点が であれば、全ての正の偶数で証明できる。バリエーションとしては、 から で正の偶数を証明し、 から で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、 から と を両方証明し、全ての整数で成立することを証明するというのもある。
仮定として だけでなく から までのすべて（もしくは一部）を用いる。これを完全帰納法（、これは同じく完全帰納法と訳される perfect induction とは別物）もしくは累積帰納法（）という。
無限降下法とは、次のような証明のパターンのことである。
この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 が通常の大小関係 によって整列されていることによる。 が 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づける事で数学的帰納法を適応できる事がある。例えば直積集合 上に辞書式順序
を入れる事で 上でも数学的帰納法が使える。
次の等式が成り立つという命題を とし、この命題が任意の自然数 について成立することを数学的帰納法を用いて証明する。
まず、 は右辺を計算することで、正しいことが確かめられる。
次に、任意の自然数 "k" をとる。"P"("k") は下記の通りであり、これが成立すると仮定する。
これが成立することを使いて "P"("k" + 1) の左辺を計算すると、"P"("k" + 1) も成立することが分かる。
以上から、数学的帰納法により、任意の自然数 "n" について命題 "P"("n") が成立する。
数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこにギャップがあったのかを説明する。前述の説明では、まず我々は "P"(1) を結論づけ、次に (a), (b) から "P"(2) を結論づけ、さらにそれと (c) を組み合わせる事で "P"(3) を結論づけ、さらにそれと(d)を組み合わせる事で "P"(4) を結論づけた。以上の議論から分かるように、"P"(2) を結論づける為には2ステップの推論、"P"(3) を結論づけるには3ステップの推論、…、"P"(100) を結論づけるには100ステップの推論が必要となる。
従って有限回のステップでは有限個の "n" に対してしか "P"("n") を結論づける事ができず、「無限個ある自然数全てに対して "P"("n") が成り立つ」という数学的帰納法の結論について"有限の長さの証明"が与えられたとはいえない。これが前述した直観的説明におけるギャップである。
そこで、ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。
集合論の枠組みでは、数学的帰納法の原理を次のように表すことができる。
この原理からもともとの形の数学的帰納法が導かれることは，次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 "P"("n") が与えられたとする。自然数の部分集合 "A" を "A" = { "n" ∈ N : ¬ "P"("n") } によって定める。この "A" が空集合であるということを示したい。そうでないと仮定すると、"A"に属する最小の自然数 "a" を取ることができるが、"P"(0)は成り立っていることから "a" は0でない。従って、ある自然数 "b" について "a" = "b" + 1となっているが、"a" は "A" に属する最小の自然数であったということから、"b" ∉ "A" であり、"P"("b") は成り立つことになる。帰納法の仮定から "P"("a") も成り立つことになり、これは矛盾である。
逆に、「"n" 以下の任意の自然数 "k" について "k" ∉ "A"」という形の命題 "P"("n") を考えることで、数学的帰納法から上の原理を導くことができる。"A" を自然数のある集合とし、"A" に属する最小の自然数が存在しないと仮定する。もし "P"(0) が成り立たないと、0 が "A" に属する最小の自然数となって仮定に反するから、"P"(0) は成り立つ。"P"("n") が成り立つとし、もし "P"("n" + 1) が成り立たないとすると、"n" + 1 が "A" の最小の自然数となって仮定に反するから、"P"("n" + 1) も成り立つ。よって数学的帰納法により "A" は空となる。
上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。ただし、"" は で定義される二項関係とする。
(1) は整列集合であるから順序 "" について最小元を持つ。これを、 とする。定理の条件において と置けば、 を満たす の元は存在しないので、「 を満たす の全ての元 について が真」という命題は無条件に真であり、従って、定理の条件を満たすためには は真でなければならない。
(2) つぎに超限帰納法の言明が偽と仮定する。これはある整列集合および、その上で定義された命題関数 "P" の組が存在して、定理の条件を満たしても "P"("x") が偽となる "A" の元 "x" が存在することを意味する。"P"が偽となる "A" の元全ての集合を "A" とする。"A" は整列集合であるからその部分集合である "A" も最小元を持つ。これを "a" とする。当然 "P"("a") は偽である。
(3) (1)で証明したように、定理の条件を満たしている限り "A" の最小元 について は真であるから "a" は ではあり得ない。従って、"A" = {"x" | "x" ∈ "A" ∧ "x" < "a"} と置けば、"A" は空ではない (少なくとも "a" を含む)。
(4) "a" は "P" が偽となる "A" の最小元であるから、"x" ∈ "A" であれば、"P"("x") は真である。従って、定理の条件により "P"("a") は真とならねばならないが、これは前言と矛盾する。
(5) 以上から、定理の条件を満たしても "P"("x") が偽となる "x" ∈ "A" が存在するような整列集合 "A" と、その上で定義される命題関数 "P" の組は存在し得ないことになる。従って超限帰納法の言明は真である。
無限下降列が存在しない二項関係を整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法（）という。
超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。
数学的帰納法を意図的に誤用したジョークとして、次のようなものがある：
以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス () が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)に帰せられる。これは砂山のパラドックスの起源としても知られる。
前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。
初期の例としては、プラトンによるパルメニデス（紀元前 370年）において暗黙に帰納法を使用した証明がみられる。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、バースカラ2世による "" に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、砂山のパラドックスにみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。
等差数列について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろにによる ""al-Fakhri"" に扱われている。al-Karaji は二項定理やパスカルの三角形を示すのに数学的帰納法を用いた。
しかし、これらの古代の数学者たちは帰納法の仮定を明示することはしていない。別の似た例としては(Freudenthal が注意深く示したように、Vacca が著したものとは対立するが)、が 1575年の著作 ""Arithmeticorum libri duo"" にて最初の "n" 個の奇数の和が "n" に等しいことを示す際にこの技術を用いている。明示された形での数学的帰納法の原理はパスカルがその著作 ""Traité du triangle arithmétique"" (1655)にて与えた。フランス人フェルマーは、帰納法と関連する、無限降下法による間接的な証明をうまく使っている。帰納法の仮定はヤコブ・ベルヌーイによっても使われ、以後多少よく知られるようになった。現代的な厳密さをもち体系的な数学的帰納法の原理の扱いは 19世紀に入ってジョージ・ブール、オーガスタス・ド・モルガン、チャールズ・サンダース・パース、ジュゼッペ・ペアノ、 リヒャルト・デーデキントによって為された。