数学归纳法

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

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

定义

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

证明 “当n = 0时命题成立。” (选择数字0因其作为自然数集合中中最小值)
证明 “若假设在n = m时命题成立，可推导出在n = m+1时命题成立。（m代表任意自然数）”

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

证明 “第一张骨牌会倒。”
证明 “只要任意一张骨牌倒了，其下一张骨牌也会因为前面的骨牌倒而跟着倒。”

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

例子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)的右手边

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

也就是说

$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也成立） ${\displaystyle 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)

数学归纳法的变体

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

从0以外的自然数开始

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

第一步，证明当n = b时命题成立。
第二步，证明如果n = m（m ≥ b）成立，那么可以推导出n = m+1也成立。

用这个方法可以证明诸如“当n ≥ 3时，n² > 2n”这一类命题。

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

第一步，证明当n =0，1，2，… b时命题成立。
第二步，证明如果n = m（m ≥ b）成立，那么可以推导出n = m+1也成立。

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

只针对偶数或只针对奇数

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

奇数方面：

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

偶数方面：

第一步，证明当n = 0或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,...,m”这样的命题，如果对一般的n比较复杂，而n=m比较容易验证，并且我们可以实现从k到k-1的递推，k=1,...,m的话，我们就能应用归纳法得到对于任意的n=0,1,2,...,m，原命题均成立。

完整归纳法

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

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

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

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

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

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

定义P（n）是我们将证的式子,
P（0）和P（1）成立
P（m + 1）在P（m）和P（m − 1）成立时成立。

结论：P（n）对一切自然数n成立。

超限归纳法

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

证明如果式子在所有的n < m成立，那么式子在当n = m时也成立.

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

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

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

m是一个极小元素，也就是没有一个元素小于m
m有一个直接的前辈，比m小的元素有一个大的元素
m没有任何前辈，也就是m是一个界限序数.

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

形式写法

使用二阶逻辑

二阶逻辑可捕捉数学归纳法这概念，表达成如下逻辑式：

\displaystyle\forall P\Bigl( P(0) \land \forall k \bigl( P(k) \to P(k+1)\bigr ) \to \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₁、P₂、P₃ ，则原先以二阶逻辑描述的公设可改写为：

\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)，且所得之自然数模型无限大。根据勒文海姆-斯科伦定理，用一阶逻辑表达的理论若有可数无限大的模型，则其有不可数大的模型，是故无法前头将所述的模型公设化^[4]。亦即，用二阶逻辑表达的公设仅允许一群模型彼此同构，而一阶逻辑模型则因前述定理，并非每个模型都同构。

使用一阶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集合论直接定义自然数，使得归纳法本身是定理而非公设。

数学归纳法的合理性

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

参见

参考文献

↑ Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26] （英语）.
↑ Matt DeVos. Mathematical Induction (PDF). 西门菲莎大学（英语）.
↑ Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大学. [2019-02-10] （英语）.
↑ Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286–287. ISBN 1-85233-921-7 （英语）.
↑ Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03] （英语）.

外部链接

Mathematical Induction, Examples （英文）

[1] Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26] （英语）.

[2] Matt DeVos. Mathematical Induction (PDF). 西门菲莎大学（英语）.

[3] Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大学. [2019-02-10] （英语）.

[4] Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286–287. ISBN 1-85233-921-7 （英语）.

[5] Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03] （英语）.

[1]

[2]

[3]

[4]

[5]

定义

例子1

证明