数学归纳法

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

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

定义

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

 

骨牌一个接一个倒下，就如同一个值到下一个值的过程

1. 证明 “当${\displaystyle n=1}$ 时命题成立。”（选择数字1因其作为自然数集合中中最小值）
2. 证明 “若假设在${\displaystyle n=m}$ 时命题成立，可推導出在${\displaystyle n=m+1}$ 时命题成立。（${\displaystyle m}$ 代表任意自然数）”

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

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

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

例子1

证明下面这个给定公式（命题）为真：

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

其中${\displaystyle n}$ 为任意自然数。这是用于计算前n个自然数的和的简单公式。证明这个公式成立的步骤如下。

证明

第一步-起始步骤

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

第二步-推递步骤

第二步证明假设${\displaystyle n=m}$ 时公式成立，则可推理出${\displaystyle n=m+1}$ 时公式也成立。

证明步骤如下。

假设${\displaystyle n=m}$ 时公式成立。即

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

然后在等式等号两边分别加上${\displaystyle m+1}$ 得到

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

这就是${\displaystyle n=m+1}$ 时的等式。

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

${\displaystyle ={\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}}.}$ 

也就是说

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

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

解释

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

1. 首先证明命题${\displaystyle P(1)}$ 成立，即公式在${\displaystyle n=1}$ 时成立。
2. 然后证明从命题${\displaystyle P(m)}$ 成立可以推演出命题${\displaystyle P(m+1)}$ 也成立。【此部实际属于演绎推理法。技术方法是基于命题${\displaystyle P(m+1)}$ 的符号形式变换出命题${\displaystyle P(m)}$ 的符号形式】
3. 根据上两条从命题${\displaystyle P(1)}$ 成立可以推理出命题${\displaystyle P(1+1)}$ ，也就是命题${\displaystyle P(2)}$ 成立。
4. 继续推理，可以知道命题${\displaystyle P(3)}$ 成立。
5. 从命题${\displaystyle P(3)}$ 成立可以推导出命题${\displaystyle P(4)}$ 也成立。
6. 不断的重复推導下一命題成立的步驟。（这就是所谓“归纳”推理的地方）
7. 我们便可以下结论：对于任意自然数${\displaystyle n}$ ，命题${\displaystyle P(n)}$  成立。

例子2

证明对于Fibonacci数列，定義${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ ，且${\displaystyle F_{0}=0,F_{1}=1}$ ，則${\displaystyle F_{0}+F_{1}+F_{2}+\cdots +F_{n}=F_{n+2}-1}$ 。

证明

首先，我们先使得${\displaystyle n=0}$ 的情况成立，${\displaystyle F_{0}=F_{2}-1,0=1-1=0}$  然后，我们假定${\displaystyle n=k}$ 的情况下的成立的，${\displaystyle F_{0}+F_{1}+...+F_{k}=F_{k+2}-1}$  然后我们使得${\displaystyle n=k+1}$ 的情况也成立，（这是为了表明，如果有任意数k使得其成立，则有其+1也成立） ${\displaystyle F_{0}+F_{1}+...+F_{k}+F_{k+1}=F_{k+2}-1+F_{k+1}=F_{k+3}-1}$  于是我们得证，即从${\displaystyle n=0}$ ，到${\displaystyle n=0+1,1+1,2+1}$ 到所有正实数都成立，就像多米诺骨牌的第一块${\displaystyle n=0}$ 成立而且每一块的下一块都成立（${\displaystyle k,k+1}$ )

数学归纳法的变体

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

从0以外的自然数开始

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

1. 第一步，证明当${\displaystyle n=b}$ 时命题成立。
2. 第二步，证明如果${\displaystyle n=m}$ （${\displaystyle m\geq b}$ ） 成立，那么可以推导出${\displaystyle n=m+1}$ 也成立。

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

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

1. 第一步，证明当${\displaystyle n=0,1,2,\cdots ,b}$ 时命题成立。
2. 第二步，证明如果${\displaystyle n=m}$ （${\displaystyle m\geq b}$ ）成立，那么可以推导出${\displaystyle n=m+1}$ 也成立。

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

只針對偶数或只針對奇数

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

奇数方面：

1. 第一步，证明当${\displaystyle n=1}$ 时命题成立。
2. 第二步，证明如果${\displaystyle n=m}$ 成立，那么可以推导出${\displaystyle n=m+2}$ 也成立。

偶数方面：

1. 第一步，证明当${\displaystyle n=0}$ 或2时命题成立。
2. 第二步，证明如果${\displaystyle n=m}$ 成立，那么可以推导出${\displaystyle n=m+2}$ 也成立。

或調整命題表述，使之變為對所有正整數成立，例如

證明「${\displaystyle 1+3+5+7+\cdots +a={\frac {(a+1)^{2}}{4}}}$ 對所有正奇數${\displaystyle a}$ 成立」等價於證明「${\displaystyle 1+3+5+7+\cdots +(2b-1)=b^{2}}$ 對所有正整數${\displaystyle b}$ 成立」。

递降归纳法 又名 遞迴歸納法

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

完整归纳法

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

1. 证明当${\displaystyle n=0}$ 时式子成立.
2. 证明当${\displaystyle n\leq m}$ 时成立，那么当${\displaystyle n=m+1}$ 时式子也成立.

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

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

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

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

1. 定义${\displaystyle \mathrm {P} (n)}$ 是我们将证的式子,
2. ${\displaystyle \mathrm {P} (0)}$ 和${\displaystyle \mathrm {P} (1)}$ 成立
3. ${\displaystyle \mathrm {P} (m+1)}$ 在${\displaystyle \mathrm {P} (m)}$ 和${\displaystyle \mathrm {P} (m-1)}$ 成立时成立。

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

超限归纳法

主条目：超限歸納法

最后两步可以用这样一步表示：

1. 证明如果式子在所有的${\displaystyle n<m}$ 成立，那么式子在当${\displaystyle n=m}$ 时也成立.

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

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

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

1. ${\displaystyle m}$ 是一个极小元素，也就是没有一个元素小于${\displaystyle m}$ 
2. ${\displaystyle m}$ 有一个直接的前辈，比${\displaystyle m}$ 小的元素有一个大的元素
3. ${\displaystyle m}$ 没有任何前辈，也就是${\displaystyle m}$ 是一个界限序数.

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

形式寫法

使用二階邏輯

二階邏輯可捕捉數學歸納法這概念，表達成如下邏輯式：

${\displaystyle \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 )}}$ ，

${\displaystyle P(.)}$ 是容納一自然數的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），${\displaystyle k}$ 與${\displaystyle n}$ 則是自然數變元，遍歷所有自然數。

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

使用一階邏輯

若用一階邏輯將數學歸納法公設化，則須採用公設模式，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為${\displaystyle P_{1}}$ 、${\displaystyle P_{2}}$ 、${\displaystyle P_{3}}$  ，則原先以二階邏輯描述的公設可改寫為：

${\displaystyle \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 \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 \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)，且所得之自然數模型無限大。根據勒文海姆-斯科倫定理，用一階邏輯表達的理論若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化^[4]。亦即，用二階邏輯表達的公設僅允許一群模型彼此同構，而一階邏輯模型則因前述定理，並非每個模型都同構。

使用一階ZFC集合論

一階ZFC集合論不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：

${\displaystyle \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 )}}$ 

${\displaystyle A}$  本身是集合，但可視作命題——只要命題在這數下成立，數字就會收入集合。別於皮亞諾公設，將數學歸納法定為公設，ZFC集合論直接定義自然數，使得歸納法本身是定理而非公設。

数学归纳法的合理性

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

參見

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

參考文獻

1. Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26]. （原始内容于2011-05-24） （英语）. 
2. Matt DeVos. Mathematical Induction (PDF). 西門菲莎大學 （英语）. 
3. Gerardo con Diaz. (PDF). 哈佛大學. [2019-02-10]. （原始内容 (PDF)存档于2013-05-02） （英语）. 
4. Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286-287. ISBN 1-85233-921-7 （英语）. 
5. (PDF). [2019-02-03]. （原始内容 (PDF)存档于2017-11-19） （英语）. 

外部链接

• Mathematical Induction, Examples （页面存档备份，存于互联网档案馆）（英文）