数学的帰納法（すうがくてききのうほう、英: 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} は存在しない。