数学归纳法

我们之前提到的归纳原理是关于正整数的一个命题。它叙述如下：

归纳原理。 设 $P (n)$ 是关于正整数 $n$ 的一个断言。假设：

(a) 断言 $P (1)$ 为真；

(b) 若断言 $P (k)$ 对给定的整数 $k$ 为真，则断言 $P (k + 1)$ 也为真。

那么断言 $P (n)$ 对所有 $n$ 都成立。

如果我们稍微思考一下，就会发现这完全符合我们的直觉。有多种模型可以帮助我们形象化这个原理。在其中一个模型中，我们考虑一组竖立的多米诺骨牌，它们排成一列，使得如果任何一张向前一张的方向倒下，它就会推倒下一张，使其再倒向下下张。这就是假设 (b) 的类比。而 (a) 的类比就是我们可以推倒第一张骨牌。但随后它会推倒第二张，第二张又会撞到第三张，……。通过写下足够多这样的步骤，我们可以到达任何指定的一张骨牌，或者说对任何给定的 $n$ 到达断言 $P (n)$ 。然而，我们现在已经看到，假设 (a) 和 (b) 正是这个过程的关键所在，而只需证明它们成立，我们就可以省去所有这些书写。

举个例子，让我们用归纳法来证明一个我们熟悉的算术级数求和公式：

1 + 2 + \dots + n = \frac{n (n + 1)}{2} .

于是 $P (n)$ 即为如下命题：前 $n$ 个整数之和等于 $\frac{n (n + 1)}{2}$ 。因此 $P (1)$ 说的是第一个整数之和，也就是 1，等于 $\frac{1 (1 + 1)}{2} = 1$ 。所以假设 (a) 满足。现在假设 (b) 以“若 $P (k)$ 为真，”开始。这意味着我们必须假定 $P (k)$ 为真，然后看 $P (k + 1)$ 的真性是否是这个假设的推论。于是我们从假定

P (k) : 1 + 2 + \dots + k = \frac{k (k + 1)}{2} .

开始。然后我们必须考虑和式

1 + 2 + \dots + k + (k + 1) = (1 + 2 + \dots + k) + (k + 1) .

但根据我们的假设，

1 + 2 + \dots + k = \frac{k (k + 1)}{2} = (k + 1) \cdot \frac{k}{2} .

因此

1 + 2 + \dots + k + (k + 1) = (k + 1) (\frac{k}{2} + 1) = (k + 1) (\frac{k + 2}{2}),

即

1 + 2 + \dots + (k + 1) = \frac{(k + 1) ((k + 1) + 1)}{2},

这正是 $P (k + 1)$ 。于是 (a) 和 (b) 都满足，由归纳法知 $P (n)$ 对所有 $n$ 成立。

习题

习题 1.

证明 $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

习题 2.

证明

习题 3.

证明

习题 4.

证明假设 (b) 对 $P (n) : n = n + 2,$ 满足，而这显然是假的。

习题 5.

举一个 $P (n)$ 的例子，使得它在 $n > 1$ 时为假，但假设 (a) 成立。

习题 6.

证明 $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}, n = 1, 2, 3, \dots .$

习题 7.

证明
$(1 - \frac{1}{4}) (1 - \frac{1}{9}) (1 - \frac{1}{16}) \dots (1 - n^{- 2}) = \frac{n + 1}{2 n}$

其中 $n = 2, 3, 4, \dots .$