数学归纳法

数学归纳法（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.$ 它和一般的数学归纳法的区别是：超限归纳法可以推广到无穷，例如对一个无穷函数空间，归纳过程可以是从一个有限子空间开始，每次向上推一维，最终得到对于整个空间成立的命题。这种归纳法必须依赖于良序公理。