数学归纳法

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

需要留意的是，数学归纳法虽然名字中有“归纳”，但是实际上数学归纳法并不属于不严谨的归纳推理法，实际上是属于完全严谨的演绎推理法。

[编辑] 定义

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

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

1. 证明当 n = 0 时命题成立。
2. 证明如果在 n = m 时命题成立，那么可以推导出在 n = m+1 时命题也成立。（m 代表任意自然数）

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

1. 证明第一张骨牌会倒。
2. 证明只要任意一张骨牌倒了，那么与其相临的下一张骨牌也会倒。

那么便可以下结论：所有的骨牌都会倒。

[编辑] 例子

假设我们要证明下面这个公式（命题）：

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

[编辑] 证明

[编辑] 第一步

第一步证明的是这个公式在 n = 0 时是否成立。这里要注意的是 0 = 0，而 0(0 + 1) / 2 = 0，所以这个公式在 n = 0 时成立。证明的第一步完成。

[编辑] 第二步

第二步我们需要证明如果假设 n = m 时公式成立，那么可以推导出 n = m+1 时公式也成立。证明步骤如下。

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

（等式 1）

然后在等式等号两边分别加上 m + 1 得到

（等式 2）

这就是 n = m+1 时的等式。我们现在需要根据等式 1 证明等式 2 成立。通过因式分解合并，等式 2 的右手边

也就是说

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

[编辑] 解释

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

1. 首先证明 P(0) 成立，即公式在 n = 0 时成立。
2. 然后证明从 P(m) 成立可以推导出 P(m+1) 也成立。（这里实际应用的是演绎推理法）
3. 根据上两条从 P(0) 成立可以推导出 P(0+1)，也就是 P(1) 成立。
4. 继续推导，可以知道 P(2)、P(3) 也成立。
5. 从 P(3) 成立可以推导出 P(4) 也成立。
6. 等等等等，不断重复。（这就是所谓“归纳”推理的地方）
7. 我们便可以下结论：对于任意自然数 n，P(n) 成立。

[编辑] 数学归纳法的变体

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

[编辑] 从 0 以外的数字开始

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

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

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

[编辑] 完整归纳法

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

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

例如,这种方法被用来证明:

fib(n) = [Φⁿ − (−1/Φ)ⁿ ] / 5^1/2

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

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

定义 P(n) 是我们将证的式子,

接着用这个规则证明也就是等价于证明

式子用开始两步证明当n属于自然数时, '所有的m ≤ n 存在时 P(m) 成立 '

[编辑] 超限归纳法

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

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

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

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

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

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

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

[编辑] 数学归纳法的证明或再形成

数学归纳法的原理作为自然数公理,通常是被规定了的(参见皮亚诺公理). 但是他可以用一些逻辑方法证明; 比如, 如果下面的公理:

自然数集是良序的。

被使用.

注意到有些其他的公理确实的是数学归纳法原理中的二者择一的公式化. 更确切地说, 两个都是等价的.参见数学归纳法的证明.

[编辑] 相关条目

归纳推理法

演绎推理法

结构归纳法

[编辑] 外部链接

• Mathematical Induction, Examples[英文]