数学的帰納法（すうがくてききのうほう、英: mathematical induction）は、数学における証明の手法の一つである。

例えば自然数に関する命題 P(n) が全ての自然数 n に対して成り立つことを証明するために、次のような手続きを行う[注 1]。
P(1) が成り立つことを示す。

任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つことを示す。

1と2の議論から任意の自然数 n について P(n) が成り立つことを結論づける。

概要

自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。

なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが伝播されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた[1]。ジョン・ウォリスによって、彼の著作Arithmetica Infinitorumの中で、この方法にinductionという名前が与えられたとされる[2][3]。
直観的説明

高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。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 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
証明

数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理�X[注 2]が数学的帰納法の原理そのものを表している。もし、公理Vを用いて、数学的帰納法をあえて証明するならば、以下のように示すことができる。

　自然数の集合を N {\displaystyle \mathbb {N} } とし、命題 P ( n ) {\displaystyle P(n)} が成り立つ n {\displaystyle n} の集合を M {\displaystyle M} とする。

　　　　　　　　　　　　　 M ≡ { n ∈ N ∣ P ( n ) } {\displaystyle M\equiv \{n\in \mathbb {N} \mid P(n)\}}

　(1) 数学的帰納法の仮定により、 1 {\displaystyle 1} は M {\displaystyle M} の要素である。

　　　　　　　　　　　　　 1 ∈ M {\displaystyle 1\in M}

　(2) 任意に自然数 r {\displaystyle r} をとる。 r ∈ M {\displaystyle r\in M} を仮定すると、 M {\displaystyle M} の定義によって P ( r ) {\displaystyle P(r)} が成り立つ。このとき、数学的帰納法の手順より、 P ( r + 1 ) {\displaystyle P(r+1)} も成り立つ。ふたたび、 M {\displaystyle M} の定義によって r + 1 ∈ M {\displaystyle r+1\in M} である。これにより ∀ r . r ∈ M ⇒ r + 1 ∈ M {\displaystyle \forall r.\,r\in M\Rightarrow r+1\in M} が示されたことになる。

　(1) および (2) により、ペアノの公理Vによって N ⊆ M {\displaystyle \mathbb {N} \subseteq M} が得られる。部分集合の定義により、これは ∀ n ∈ N . P ( n ) {\displaystyle \forall n\in \mathbb {N} .\,P(n)} であることを意味する。(証明終)
バリエーション

数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
1以外から始める

変数変換によって明らかなように、変数 n が表す範囲は n → n + 1 という操作で閉じていれば {1, 2, ...} である必要はなく、0 を自然数に含めることにしたり、あるいは任意の整数 m に関する {m, m + 1, ...} という範囲でもよいことになる。
+1以外

例えば n → n + 1 ではなく、n → n + 2 で証明し、開始点が P(2) であれば、全ての正の偶数で証明できる。バリエーションとしては、P(2) から n → n + 2 で正の偶数を証明し、P(1) から n → n + 2 で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、P(0) から n → n + 1 と n → n − 1 を両方証明し、全ての整数で成立することを証明するという場合もある。
先立つすべての結果を用いる

仮定として P(k) だけでなく P(1) から P(k ? 1) までのすべて（もしくは一部）を用いる。これを完全帰納法（英: complete induction、これは同じく完全帰納法と訳される perfect induction とは別物）もしくは累積帰納法（英: course of values induction）という。任意の自然数 k をとったとき、k より真に小さなすべての自然数 m に対して P(m) が真であれば、P(k) も真である[注 3]。よって任意の自然数 n について P(n) は真である。
背理法を組み合わせたもの詳細は「無限降下法」を参照

無限降下法とは、背理法を用いて ∀ n ∈ N . P ( n ) {\displaystyle \forall n\in \mathbb {N} .\,P(n)} を証明する、次のようなパターンのことである。 P ( n ) {\displaystyle P(n)} が成立しないような自然数 n {\displaystyle n} が存在すると仮定し、その中で最小のものを k {\displaystyle k} とする。次に、 P ( k ) {\displaystyle P(k)} を仮定すると、「ある自然数 k ′ < k {\displaystyle k'<k} が存在して P ( k ′ ) {\displaystyle P(k')} ではないこと」を導けることを示す。これは k {\displaystyle k} の最小性に矛盾するから、背理法により、 P ( n ) {\displaystyle P(n)} が成立しないような自然数 n {\displaystyle n} は存在しない。すなわち、すべての自然数 n {\displaystyle n} に対して P ( n ) {\displaystyle P(n)} が成り立つ。

この議論と前に述べた「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N {\displaystyle \mathbb {N} } が通常の大小関係 < {\displaystyle <} によって整列されていることによる。 < {\displaystyle <} が N {\displaystyle \mathbb {N} } 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
より一般の集合への拡張

数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づけることで数学的帰納法を適用できることがある。例えば直積集合 N × N 上に辞書式順序(x, y) > (x′, y′): ⇔ (x > x′) または (x = x′ かつ y > y′)

を入れることで N × N 上でも数学的帰納法が使える。
数学的帰納法の例

次の等式が成り立つという命題を P(n) とし、この命題が任意の自然数 n について成立することを数学的帰納法を用いて証明する。 1 + 2 + ⋯ + n = n ( n + 1 ) 2 . {\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}.}

まず、P(1) は右辺を計算することで、正しいことが確かめられる。右辺 = (1(1+1))/2 = 1 = 左辺。

次に、任意の自然数 k をとる。P(k) は下記の通りであり、これが成立すると仮定する。 1 + 2 + ⋯ + k = k ( k + 1 ) 2 . {\displaystyle 1+2+\cdots +k={\frac {k(k+1)}{2}}.}

これが成立することを使い、 P(k + 1) の左辺を計算すると、P(k + 1) も成立することが分かる。 1 + 2 + ⋯ + k + ( k + 1 ) = ( 1 + 2 + ⋯ + k ) + ( k + 1 ) = k ( k + 1 ) 2 + ( k + 1 ) = ( k + 1 ) ( k + 2 ) 2 {\displaystyle 1+2+\cdots +k+(k+1)=(1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}}

以上から、数学的帰納法により、任意の自然数 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) が成り立つ」という数学的帰納法の結論について有限の長さの証明が与えられたとはいえない。これが前述した直観的説明におけるギャップである。

そこで、ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。