数学归纳法——原理、步骤与例题

数学归纳法是一种证明方法，用来说明某个命题从某个起始整数开始，对之后的每一个整数都成立。要证明一个命题对所有 $n \ge n_0$ 都成立，你需要先证明第一个情形成立，再证明如果它对某个整数成立，那么它对下一个整数也成立。

如果这两部分都正确，那么该命题就在所给范围内对每个整数都成立。这就是数学归纳法的核心思想。

数学归纳法如何运作

把命题写成 $P(n)$。那么归纳法的结构如下：

1. 证明基础情形：说明 $P(n_0)$ 成立。
2. 证明归纳步骤：说明对于任意整数 $k \ge n_0$，如果 $P(k)$ 成立，那么 $P(k+1)$ 也成立。

完成这两步后，就可以得出结论：$P(n)$ 对每个整数 $n \ge n_0$ 都成立。

它的逻辑是逐步推进的。基础情形启动整条链，归纳步骤则让这条链按整数一个接一个地延续下去。

为什么基础情形和归纳步骤都很重要

基础情形给出第一个为真的命题。归纳步骤说明真值会从一个整数传递到下一个整数。

所以如果 $P(n_0)$ 成立，那么 $P(n_0 + 1)$ 也成立。接着 $P(n_0 + 2)$ 也成立，以此类推。数学归纳法既不能跳过起点，也不能跳过从一个情形到下一个情形之间的连接。

例题：用归纳法证明求和公式

一个标准例子是公式

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

它对所有整数 $n \ge 1$ 都成立。

设

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

基础情形

取 $n = 1$。左边是 $1$，右边是

$$\frac{1(1+1)}{2} = 1$$

所以 $P(1)$ 成立。

归纳步骤

假设对于某个任意整数 $k \ge 1$，$P(k)$ 成立。这意味着

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

现在证明 $P(k+1)$。从 $k+1$ 时左边的表达式开始：

$$1 + 2 + 3 + \cdots + k + (k+1)$$

利用归纳假设，可得

$$\frac{k(k+1)}{2} + (k+1)$$

提取公因式 $(k+1)$：

$$(k+1)\left(\frac{k}{2} + 1\right)$$

再化简：

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

这正好就是当 $n = k+1$ 时的公式。因此 $P(k+1)$ 成立。

由于基础情形和归纳步骤都已证明，所以该公式对所有整数 $n \ge 1$ 都成立。

什么时候使用数学归纳法

当一个命题依赖于整数参数，并且每一种情形都自然地与前面的情形相联系时，归纳法就很有用。这种情况常见于求和、整除性命题、不等式、递推关系以及算法证明。

首先，要找出正确的起始值。有些命题从 $n = 0$ 开始，有些从 $n = 1$ 开始，还有些只有在更大的整数范围内才有意义。

然后检查下一个有效情形是什么。通常是从 $k$ 推到 $k+1$，但如果命题只讨论偶数，那么从 $k$ 推到 $k+2$ 可能才是正确的形式。

归纳证明中的常见错误

只证明基础情形

基础情形只检查第一个值。仅凭这一点，并不能证明该命题对后面的整数也成立。

使用了错误的起始值

如果命题是针对所有 $n \ge 2$，那么只证明 $P(1)$ 并没有帮助。基础情形必须与命题真正适用的范围一致。

不严谨地使用归纳假设

在归纳步骤中，你是假设定义域内某个任意整数 $k$ 的 $P(k)$ 成立。你并不是在假设整个定理已经被证明了。

证明了错误的下一步

如果你的定理需要的是从 $k \to k+1$ 的步骤，那么证明别的步骤并不能完成论证，除非你进一步解释为什么那个不同的步骤已经足够。

一个有用的扩展：强归纳法

有时要证明 $P(k+1)$，仅仅知道 $P(k)$ 还不够。在这种情况下，强归纳法允许你假设直到 $k$ 为止的所有更早情形都成立，然后再证明下一个情形。

它的思想与普通归纳法密切相关，只是所作的假设更强。例如，当证明依赖于把一个数拆分成更小的部分时，它就很有用。

自己试一试

考虑命题

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

并用同样的结构证明它对所有整数 $n \ge 1$ 都成立：先证明基础情形，再证明从 $k$ 到 $k+1$ 的步骤。如果你能把这个证明清楚地写出来，通常就真正掌握这种方法了。