5. 归纳

归纳法（Induction） 是证明某一特征对全体非负整数成立的重要方法。事实上，归纳法的使用可以区分连续与离散两种数学特征——只能在离散量上应用归纳法。本节介绍两种最常用的归纳法：一般归纳法（又称第一数学归纳法）与 强归纳法（又称第二数学归纳法）。

一般归纳法

令 $P (n)$ 是定义在 $N$ 上的谓词，一般归纳法指出，若 $P (0)$ 为真，且对 $\forall n \in N . P (n) \to P (n + 1)$ ，则 $P (n)$ 在整个 $N$ 上成立。形式化的表达为：

P (0), \forall n \in N . P (n) \to P (n + 1) ⊢ \forall m \in N . P (m)

使用归纳法证明命题的模板如下：

陈述使用归纳法进行证明。
定义适当的谓词 $P (n)$ ， $P (n)$ 被称作 归纳假设。我们最终要证明 $P (n)$ 在整个 $N$ 上成立。有时 $P (n)$ 会涉及多个自变量，需要根据题意指出 $n$ 代表哪个变量。
证明基本情形 $P (0)$ 成立。
进行 归纳步骤，证明 $\forall n \in N . P (n) \to P (n + 1)$ 成立。证明过程便是假设 $P (n)$ 成立，并由之推出 $P (n + 1)$ 也成立。
得出结论。

有时可能会要求证明命题在 $n \geq a$ 上而非整个 $N$ 上成立，此时我们需要对基本情形和归纳步骤中 $n$ 的范围做简单修改，但这样并不会影响一般归纳法的正确性。

此外，有时当我们直接利用一般归纳法证明某个命题时可能会遭遇困难，此时可以考虑证明比原命题更强的命题，这有一些反直觉。但事实上，当我们证明更强的命题时，提出的归纳假设因此也变得更强了，可能导致证明过程变简单。当然提出的归纳假设必须为真，否则证明没有意义。

例题

证明对任意 $n, q \in Z, q \neq 1$ ，

\sum_{i = 0}^{n} q^{i} = \frac{q^{n + 1} - 1}{q - 1}

解答

使用归纳法证明此命题。令命题 $P (n)$ 为 $\forall q \in Z, q \neq 1. \sum_{i = 0}^{n} q^{i} = \frac{q^{n + 1} - 1}{q - 1}$ 。

基本情形：对 $n = 0$ ， $\sum_{i = 0}^{0} q^{i} = q^{0} = 1$ ； $\frac{q - 1}{q - 1} = 1$ ，故 $P (0)$ 成立。

归纳步骤：假设 $P (n)$ 为真，即 $\sum_{i = 0}^{n} q^{i} = \frac{q^{n + 1} - 1}{q - 1}$ 成立，在该式左右加上 $q^{n + 1}$ ，有

\sum_{i = 0}^{n + 1} q^{i} = \frac{q^{n + 1} - 1}{q - 1} + q^{n + 1} = \frac{q^{n + 1} + q^{n + 2} - q^{n + 1} - 1}{q - 1} = \frac{q^{(n + 1) + 1} - 1}{q - 1}

则 $P (n + 1)$ 成立，依据归纳法原命题得证。

强归纳法

强归纳法与一般归纳法略有不同。强归纳法与一般归纳法都要求证明基本情况成立，但与一般归纳法不同的是，在归纳步骤，你可以假设对给定的 $n \in N$ ，对任意 $k \leq n$ 的 $P (k)$ 成立，证明 $P (n + 1)$ 成立，则 $P (n)$ 在整个 $N$ 上成立。形式化的表达为：

P (0), \forall n \in N . (\forall k \in N, k \leq n . P (k)) \to P (n + 1) ⊢ \forall m \in N . P (m)

也因此，我们可以在归纳假设阶段做更多的的假设。显然一般归纳法是强归纳法的一个特例。

例题

证明当 $a$ ， $b$ 在 $N$ 内任意取值时，式子 $3 a + 5 b$ 可以等于大于 $7$ 的任意正整数。

解答

使用强归纳法证明此命题。令命题 $P (n) \equiv \exists a, b \in N . 3 a + 5 b = n + 8$ 。

基本情形：对 $n = 0$ ，令 $a = b = 1$ ，则 $3 a + 5 b = 8$ ，故 $P (0)$ 成立。

归纳步骤：假设对于任意 $k \geq n$ ， $P (k)$ 为真，进行分类讨论：

若 $n + 1 = 1$ ，令 $a = 3, b = 0$ ，则 $3 a + 5 b = 9 = (n + 1) + 8$ 。
若 $n + 1 = 2$ ，令 $a = 0, b = 2$ ，则 $3 a + 5 b = 10 = (n + 1) + 8$ 。
若 $n + 1 \geq 3$ ，依据归纳假设， $P (n - 2)$ 为真，则 $\exists a, b \in N . 3 a + 5 b = (n - 2) + 8$ 。令 $a^{'} = a + 1$ ，则 $3 a^{'} + 5 b = 3 a + 5 b + 3 = (n - 2) + 8 + 3 = (n + 1) + 8$ 。

综上， $P (n + 1)$ 成立，依据强归纳法原命题得证。

一般归纳法、强归纳法与良序原理之间的关系

事实上，强归纳法并不比一般归纳法更强，用二者所做的证明是可以通过修改归纳假设相互转化的。然而，区分出这两种方法仍然很有必要，这样我们可以清楚地知道 $P (n + 1)$ 由谁推得。

基于良序原理的证明同样也能转化为归纳法的证明。不过归纳法证明相对更加清晰，一般不需要进行反证；基于良序原理的证明一般要更加简短。

利用归纳法和良序原理的证明都允许我们在不理解某个命题的具体含义下就证明它，同时证明过程是正确的，但坏处在于我们完成证明后可能也无法理解我们具体证明了什么，也不清楚这个命题是如何得出的。