数学归纳法（，縮寫：MI）是一种数学证明方法，通常被用于证明某个给定命题在整个或者局部自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。

虽然数学归纳法名字中有“归纳”，但是数学归纳法并非逻辑上不严谨的归纳推理法，它属于完全严谨的演绎推理法。事實上，所有數學證明都属于演繹推理方法。

定义
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

证明 “当n=1时命题成立。”（选择数字1因其作为自然数集合中的最小值）

证明 “若假设在n=m时命题成立，可推導出在n=m+1时命题成立。（m代表任意自然数）”

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺骨牌效应也许更容易理解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你可以：

证明 「第一张骨牌会倒。」

证明 「只要任意一张骨牌倒了，其下一张骨牌也会因為前面的骨牌倒而跟著倒。」

则可下结论：所有的骨牌都会倒下。

例子
例子1
证明下-{面}-这个给定公式（命题）为真：

1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}

其中n为任意自然数。这是用于计算前n个自然数的和的简单公式。

证明
第一步-起始步骤
第一步是验证这个公式在n=1时成立。左边=1，而右边=\frac{1(1+1)}{2}=1，所以这个公式在n=1时成立。第一步完成。

第二步-推递步骤
第二步证明假设n=m时公式成立，则可推理出n=m+1时公式也成立。 证明步骤如下。

假设n=m时公式成立。即

1 + 2 + \cdots + m = \frac{m(m + 1)}{2}【等式P(m)】

然后在等式等号两边分别加上m+1得到
1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)【等式P(m+1)】
这就是n=m+1时的等式。

现在需要根据等式等式P(m+1)演绎出等式P(m)的符号形式。（需要注意的是如果给定公式不为真，则做不到）通过因式分解合并(形式变换/字符操纵)，等式P(m+1)的右手边

= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2}
= \frac{(m + 2)(m + 1)}{2}
= \frac{(m + 1)(m + 2)}{2}
= \frac{(m + 1)[(m + 1) + 1]}{2}.

也就是说

1 + 2 + \cdots + (m + 1) = \frac{(m + 1)[(m + 1) + 1]}{2}

这样便证明了从等式P(m)成立可推理出等式P(m+1)也成立。证明至此完成，结论：对于任意自然数n，P(n)均成立。

解释
在这个证明中，推理的过程如下：

首先证明命题P(1)成立，即公式在n=1时成立。

然后证明从命题P(m)成立可以推演出命题P(m+1)也成立。【此部实际属于演绎推理法。技术方法是基于命题P(m+1)的符号形式变换出命题P(m)的符号形式。】

根据上两条从命题P(1)成立可以推理出命题P(1+1)，也就是命题P(2)成立。

继续推理，可以知道命题P(3)成立。

从命题P(3)成立可以推导出命题P(4)也成立。

不断的重复推導下一命題成立的步驟。（这就是所谓“归纳”推理的地方）

我们便可以下结论：对于任意自然数n，命题P(n) 成立。

例子2
证明对于Fibonacci数列，定義F_n=F_{n-1}+F_{n-2}，且F_0=0,F_1=1，則F_0+F_1+F_2+ \cdots +F_n=F_{n+2}-1。

证明
首先，我们先使得n=0的情况成立，F_{0}=F_{2}-1 ,0=1-1=0
然后，我们假定n=k的情况下的成立的，F_{0}+F_{1}+...+F_{k}=F_{k+2}-1
然后我们使得n=k+1的情况也成立，（这是为了表明，如果有任意数k使得其成立，则有其+1也成立）

F_{0}+F_{1}+...+F_{k}+F_{k+1}
=F_{k+2}-1+F_{k+1}
=F_{k+3}-1

于是我们得证，即从n=0，到n=0+1,1+1,2+1到所有正实数都成立，就像多米诺骨牌的第一块n=0成立而且每一块的下一块都成立（k,k+1)

数学归纳法的变体
在应用中，数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。

从自然数开始
第一种情况：
如果欲证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字b的自然数，那么证明的步骤需要做如下修改：

第一步，证明当n=b时命题成立。

第二步，证明如果n=m（m\geq b） 成立，那么可以推导出n=m+1也成立。

用这个方法可以证明诸如“当n\geq 5时，2^n>n^2”这一类命题。

第二种情况：
如果欲证明的命题针对全部自然数，但仅当大于等于某个数字b时比较容易证明，则可参考如下步骤：

第一步，证明当n=0,1,2,\cdots, b时命题成立。

第二步，证明如果n=m（m\geq b）成立，那么可以推导出n=m+1也成立。

用这种方法可以证明一些需要通过放缩来证明的不等式。

只針對偶数或只針對奇数
如果我们想证明的命题并不是针对全部自然数，而只是针对所有奇数或偶数，那么证明的步骤需要做如下修改：

奇数方面：

第一步，证明当n=1时命题成立。

第二步，证明如果n=m成立，那么可以推导出n=m+2也成立。

偶数方面：

第一步，证明当n=0或n = 2时命题成立。

第二步，证明如果n=m成立，那么可以推导出n=m+2也成立。

或調整命題表述，使之變為對所有正整數成立，例如
:證明「1+3+5+7+ \cdots +a=\frac{(a+1)^2}{4}對所有正奇數a成立」等價於證明「1+3+5+7+ \cdots +(2b-1)=b^2對所有正整數b成立」。

遞迴歸納法
又名递降归纳法。数学归纳法并不是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的n=0,1,2,\cdots,m”这样的命题，如果对一般的n比较复杂，而n=m比较容易验证，并且我们可以实现从k到k-1的递推，k=1,\cdots,m的话，我们就能应用归纳法得到对于任意的n=0,1,2,\cdots,m，原命题均成立。

完整归纳法
另一个一般化的方法叫完整归纳法（也称第二数学归纳法或强归纳法），在第二步中我们假定式子不仅当n=m时成立，当n小于或等于m时也成立。这样可以设计出这样两步:

证明当n=0时式子成立.

证明当n\leq m时成立，那么当n=m+1时式子也成立.

例如，这种方法被用来证明：

:\mathrm{fib}(n)=\frac{\Phi^n-\left(-\Phi\right)^{-n}}{5^{\frac{1}{2}}}

其中 \mathrm{fib}(n)是第n个斐波纳契数和\Phi =\frac{1+5^{\frac{1}{2}}}{2}（即黄金分割）。如果我们可以假设式子已经在当n=m和n=m-1时成立，从\mathrm{fib}(m+1)=\mathrm{fib}(m)+\mathrm{fib}(m-1)之后可以直截了当地证明当n=m+1时式子成立.

这种方法也是第一种形式的特殊化：

定义\mathrm{P}(n)是我们将证的式子,

\mathrm{P}(0)和\mathrm{P}(1)成立

\mathrm{P}(m+1)在\mathrm{P}(m)和\mathrm{P}(m-1)成立时成立。

结论：\mathrm{P}(n)对一切自然数n成立。

超限归纳法
最后两步可以用这样一步表示：
:证明如果式子在所有的n成立，那么式子在当n=m时也成立。

实际上这是数学归纳法的大多数通式，可以知道他不仅对表达自然数的式子有效，而且对于任何在良基集（也就是一个偏序的集合，包括有限降链）中元素的式子也有效（这里""被定义为a 当且仅当a\leq b和a\neq b）。

这种形式的归纳法当运用到序数（以良序的和一些的良基类的形式）时被称为超限归纳法，它在集合论、拓扑学和其他领域是一種重要的方法。

要区别用超限归纳法证明的命题的三种情况：

m是一个极小元素，也就是没有一个元素小于m

m有一个直接的前辈，比m小的元素有一个大的元素

m没有任何前辈，也就是m是一个界限序数.

参见数学归纳法的三种形式。

形式寫法
使用二階邏輯
二階邏輯可捕捉數學歸納法這概念，表達成如下邏輯式：
: \displaystyle\forall P\Bigl( P(0) \land \forall k \bigl( P(k) \Rightarrow P(k+1)\bigr ) \Rightarrow \forall n \bigl(P(n)\bigr)\Bigr)，
P(.)是容納一自然數的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），k與n則是自然數變元，遍歷所有自然數。

白話解釋此式，此式說：起始步驟P(0)與推遞步驟（即歸納假設，P(k)蘊涵 P(k+1)） 兩步成立會導出對任一自然數n， P(n)成立之結論。通常，我們為了證明第二步，會假設P(n)成立（歸納假設），再進一步證明P(n+1)。此牽涉到條件證法，將條件句之前件作為假設，假定其正確以便於證明。

使用一階邏輯
若用一階邏輯將數學歸納法公設化，則須採用公設模式，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為P_1、P_2、P_3 ，則原先以二階邏輯描述的公設可改寫為：
: \displaystyle P_1(0) \land \forall k \bigl( P_1(k) \to P_1(k+1)\bigr ) \to \forall n \bigl(P_1(n)\bigr)，
: \displaystyle P_2(0) \land \forall k \bigl( P_2(k) \to P_2(k+1)\bigr ) \to \forall n \bigl(P_2(n)\bigr)，
: \displaystyle P_3(0) \land \forall k \bigl( P_3(k) \to P_3(k+1)\bigr ) \to \forall n \bigl(P_3(n)\bigr)，
。然而其強度與以二階邏輯描述之邏輯式不同，前者較後者弱。理由為一階邏輯述詞之數量為可數，而二階邏輯量限所迭代的集合為不可數。

此外，二階邏輯所表示的歸納公設綜合其它皮亞諾公設為同疇(categorical)，且所得之自然數模型無限大。根據勒文海姆-斯科倫定理，用一階邏輯表達的理論若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化。亦即，用二階邏輯表達的公設僅允許一群模型彼此同構，而一階邏輯模型則因前述定理，並非每個模型都同構。

使用一階ZFC集合論
一階ZFC集合論不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：
: \forall A \Bigl( 0 \in A \land \forall k \in \mathbb{N} \bigl( k \in A \to (k+1) \in A \bigr) \to \mathbb{N}\subseteq A\Bigr)
A 本身是集合，但可視作命題——只要命題在這數下成立，數字就會收入集合。別於皮亞諾公設，將數學歸納法定為公設，ZFC集合論直接定義自然數，使得歸納法本身是定理而非公設。

数学归纳法的合理性
皮亞諾公理視數學歸納法不證自明，設作公理，而於策梅洛-弗兰克尔集合论，數學歸納法可从良序定理推导出来。需要注意的是数学归纳法只能判定给定命题的真，而不能证伪，因为在形式变换这一过程需要一定技巧与灵感。抽象的概念如自然数，可通过抽象的工具去处理。通过有限的步骤处理无限的对象如证明质数的无穷。

參見

• 归纳推理
• 演绎推理
• 结构归纳法
• 完整归纳法

參考文獻
外部链接

• [http://www.cut-the-knot.org/induction.shtml Mathematical Induction, Examples]