數學歸納法

數學歸納法（mathematical induction）是一種證明與自然數相關的定理的方法，它與自然數集合的良序公理等價，且被列入如 Peano 公理等一些和自然數相關的公理當中。數學歸納法有以下幾種形式，以下皆假設$P(m)$是一個與自然數相關（以下將與定理相關的自然數設做$m$）的命題。

第一數學歸納法

若以下兩條皆能成立，則命題$P(m)$對任意的自然數$m \geqslant 0$皆成立：

1. 若對$m = 0$（或其他自然數）時，命題$P(m)$成立。
2. 若對於任意的$m \geqslant 0$，當命題$P(m)$對$m= n$成立時，可推出命題$P(m)$對$m = n+1$亦成立。

第二數學歸納法

若以下兩條皆能成立，則命題$P(m)$對任意的自然數$m \geqslant 0$皆成立：

1. 對$m = 0$（或其他自然數）時，命題$P(m)$成立。
2. 若命題$P(m)$對任意$m \leqslant n$成立時，可推出命題$P(m)$對$m = n+1$亦成立。

第二數學歸納法的變形

若以下兩條皆能成立，則命題$P(m)$對任意的自然數$m \geqslant 0$皆成立：

1. 對$m = 1, 2$時，命題$P(m)$成立。
2. 若命題$P(k-1)$以及$P(k)$成立時，可推出命題$P(k+1)$成立。

蹺蹺板歸納法

設$P(n)$和$Q(n)$是關於自然數$n$的兩個命題。如果有以下兩點成立，則命題$P(n)$和命題$Q(n)$對任意的自然數$n$皆成立。

1. 命題$P(1)$成立；
2. 假設$P(k)$成立可以推出$Q(k)$成立，假設$Q(k)$成立也可以推出$P(k+1)$成立。

二重數學歸納法

設命題$P(m, n)$是與兩個獨立的自然數$m,n$相關的命題。如果有以下兩點成立，則命題$P(m, n)$對任意的自然數$m,n$皆成立。

1. 命題$P(1, 1)$成立。
2. 對任意自然數$k, l$，假設$P(k, l)$成立可以推出$P(k+1, l)$和$P(k, l+1)$都成立。

向後向前歸納法

對一個有關正整數$n$的數學命題$P(n)$，這個歸納法是如下的方法：

1. 命題$P(1), P(2), P(4)$成立。
2. 假設$P(2^k)$成立，去證明$P(2^{k+1})$成立。這一步跳躍的遞推過程。
3. 假設$P(n), n > 2$成立，去證明$P(n-1)$成立，這一步是將跳過的命題通過向前歸納的方式證明出來。
4. 於是得到$P(n)$對任意的$n$都成立。

這個方法是 Cauchy 首次在他的不等式證明中使用的，可用來證明樊畿不等式。

超限歸納法

它是將數學歸納法推廣到一般良序集上的結果，它是說：

若$S$為良序集$(A, \leqslant)$的一個子集，且對任意的$a \in A$，由$\{ x \in A|x < a \} \subset S$可推出$a \in S$，那麼$S = A.$ 它和一般的數學歸納法的區別是：超限歸納法可以推廣到無窮，例如對一個無窮函數空間，歸納過程可以是從一個有限子空間開始，每次向上推一維，最終得到對於整個空間成立的命題。這種歸納法必須依賴於良序公理。