第4章
强归纳法

数学归纳法是一种功能强大且应用广泛的证明方法，但在某些情况下它似乎还不够强大。这里有一个简单的例子，它融合了上一章的归纳范例，但又不完全相同。为了解答这个问题，我们需要一个更强版本的归纳法。

例4.1 有一款简单的游戏，需要两名玩家和一堆硬币。我们将两个玩家分别称作Ali和Brad。从Ali开始，然后两名玩家轮流拿硬币。游戏规则有两条：

1 . 玩家在每轮需要拿起一至两枚硬币 。

2 . 拿到最后一枚硬币的玩家失败 。

如果每名玩家都足够聪明，那么谁会赢呢？

答案取决于开始时有多少枚硬币。设硬币数量为 n ，通过尝试较小的 n 值，看看我们能否找到解决问题的模型。

• 当 n =1时，Ali失败，因为她必须拿起至少一枚硬币，但只有一枚硬币。所以她必须拿起这“最后一枚”硬币。对于Ali来说， n =1是使其必输的情况（见图4.1）。

• 如果 n =2，情况又会如何呢？Ali也可能失败，在她愚蠢地拾起两枚硬币时发生。但在分析问题之前，我们已经假定Ali和Brad都是足够聪明的。如果Ali拾起1枚硬币，就会留下1枚硬币给Brad，从而迫使他陷入必输的境地。（注意这里有一个重要的概念：如果 n 是使Ali输掉游戏的情况，那么它也可能是使Brad输掉游戏的情况，即只剩一枚硬币留给Brad。）因此，以2枚硬币开始的游戏，对Ali来说是获胜的情况，因为她可以迫使Brad陷入必输的境地（见图4.2）。

• 如果开始时有3枚硬币，那么Ali可以拾起2枚硬币，这再次使Brad陷入必输的境地。因此，以3枚硬币开始的游戏，会得到Ali获胜的情况（见图4.3）。

• 如果开始时有4枚硬币，那么Ali有两种选择，但是无论哪种选择，她都无法获胜。她可以拿起一枚硬币，留下3枚；也可以拿起两枚硬币，剩下两枚。但是接下来，比赛就交给了Brad，此时这堆硬币有3枚或者两枚，都是Brad获胜的情况（见图4.4和图4.5）。

• 再试一种情况，即在游戏开始时 n =5。Ali可以拿起一枚硬币，留给Brad4枚硬币。对Brad来说，这是一个必输的局面，就像Ali面对4枚硬币的情况一样。因此，5枚硬币是Ali获胜的情况（图4.6）。

对于一个玩家来说，面对 n 枚硬币是赢还是输似乎取决于 n 被3除时的余数是0、1还是2：

1 .如果 n 除以3的余数为0或2，那么面对 n 枚硬币就是赢的局面。

2 .如果 n 除以3的余数为1，那么面对 n 枚硬币就是必输的境地。

情况1和情况2是相互依存的。如果余数为1，那么拿起1或2枚硬币将分别创建余数为0或2的硬币堆，这是使另一方获胜的选择。也就是说，如果存在某个整数 n ，使得 n =3 k +1，那么 n -1可以被3整除，并且有

n -2=3( k -1)+2

即除以3余数为2。如果余数是0或2，那么拿起2枚或1枚硬币，将创建一个余数为1的硬币堆，这是使另一方输掉游戏的情况。

因此，我们做出以下猜想。

猜想 ：对于任意的 n ≥1，开始时有 n 枚硬币，对于Ali是输掉游戏的情况，当且仅当存在某个整数 k ，使得 n =3 k +1。

由于情况1和情况2的相互关联性，这一猜想看上去很适合用数学归纳法来描述，除了一个小小的“瑕疵”外，即 n 枚硬币的论证不仅取决于 n -1枚硬币，还取决于 n -2枚硬币的 归纳假设 。下面先给出猜想的证明，然后给出公式化的强归纳法。

解 ：我们将用归纳法对 n 进行归纳来证明前面的猜想。

归纳基础 。对于 n ₀ =1和 n ₁ =2的情况，猜想为真，因为对于Ali来说，前者（ n ₀ =3·0+1）是输掉游戏的情况，而后者（ n ₁ =3·0+2）是获胜的情况。正如前面所论述的那样。

归纳假设 。假设对于任意的 n ≥2和任意的 m ，使得1≤ m ≤ n ， m 枚硬币是使Ali输掉游戏的情况，当且仅当 m 除以3的余数为1。

归纳步骤 。假设Ali面对的是 n +1枚硬币（ n ≥2），Ali可以拿起一枚或者两枚硬币，留下 n 枚或者 n -1枚硬币给Brad。由于 n ≥2，那么 n 和 n -1是大于或等于1并且小于或等于 n 的数。

如果 n +1除以3的余数为1，则 n 和 n -1的余数分别为0和2。又由于 n 和 n -1都是小于或等于 n 的数，根据归纳假设，这两个数都是使Brad获胜的情况。因此， n +1对Ali来说是输掉游戏的情况。

如果 n +1除以3的余数为0即 n +1=3 k ，那么Ali可以拿起两枚硬币，留下 n -1=3·( k -1)+1枚硬币给Brad；又由于 n -1< n ，根据 归纳假设 ， n -1是使Brad输掉游戏的情况。

类似地，如果 n +1除以3的余数为2，Ali可以拿起一枚硬币，留下3的倍数加1枚硬币给Brad，使Brad陷入必输的境地。■

设谓词 P （ n ）表示：

以 n 枚硬币开始且使 Ali 处于输掉游戏的情况 ， 当且仅当 n 是 3 的倍数加 1。

这个论断涉及前一章中与归纳法无关的两个特别的特征。首先是已经提及的一点：为了证明 P （ n +1），对于 m ≤ n 的多个值， 归纳假设 不仅要包括 P （ n ）为真，还要包括 P （ m ）为真。（在前面的具体论证中，包括了 m = n 和 m = n -1的情况。）这里有一个有意思的比喻：爬梯子。要爬某一级台阶，不仅要爬过紧挨着这级台阶下面的一级台阶，而且要爬过这级台阶以下的所有台阶（图4.7）。当我们爬过下面的所有台阶到达某个高度时，使用爬过的任意一级台阶作为到更高台阶的基础是合理的。

另外一个重要的细节是，我们需要多个归纳基础，即在这个论断中， 归纳基础 包括 n =1和 n =2两种情况。这一点很关键，但容易被忽视。在 归纳步骤 中，我们选取了数字 n +1并从中减去1或2，然后论证“对 P （ n ）和 P （ n -1）的真值进行归纳”的假设是安全的。为了做到这一点，我们注明 n 和 n -1都是小于或等于 n 的（显而易见），并且都大于或等于1。为了使（ n +1-2）≥1，我们需要在归纳开始时假设 n ≥2，即在 归纳基础 论证时，要分别考虑 n =1和 n =2的情况。

将上述所有考虑放在一起，我们提出 强数学归纳法 （strong principle of mathematical induction）：

证明谓词 P ( n ) 对于大于或等于某个特定数 n ₀ 的任意 n 都成立 。

归纳基础 。证明 P （ m ）成立，对于任意的 m ，满足 n ₀ ≤ m ≤ n ₁ ，其中 n ₁ ≥ n ₀ 。也就是说， n ₀ 是最底层台阶，我们要分别论证对于 n ₀ 和 n ₁ 之间（包括 n ₀ 和 n ₁ ）的每个 m 有 P （ m ）成立。在硬币游戏中，有 n ₀ =1和 n ₁ =2。

归纳假设 。设对于任意的 n ≥ n ₁ ， P （ m ）成立，其中 n ₀ ≤ m ≤ n 。

归纳步骤 。设 归纳假设 成立，证明 P （ n +1）成立。

强归纳法如图4.8所示，展示了 n 为0，1，…的情况。对于 m < n ₀ 的情况， P （ m ）可以不为真。因为 归纳基础 是 n ₀ ,…, n ₁ ，所以对于该范围内的每个 m ，必须给出相对应的“ P （ m ）为真”的论证。进入 归纳步骤 阶段之前，要完成“对于 n ₀ 到 n 之间（包括 n ₀ 和 n ）的所有 m ，有 P （ m ）成立”的证明， m = n ₁ 是浅灰色值部分的归纳第一步，浅灰色范围内的所有值也都是 归纳基础。归纳步骤 （灰色部分）在已知 P （ m ）对于 n ₀ 和 n 之间的所有浅灰色值均为真的基础上证明 P （ n +1）成立。

下面的例子将展示如何使用强归纳法来证明数列的性质。

例4.2 考虑数列 a ₁ =3和 a ₂ =5，对于所有的 n >2，有 a _n =3 a _{n -1} -2 a _{n -2} 。应用强归纳法证明：对于所有的整数 n ≥1，有 a _n =2 ⁿ +1。

解 ：设谓词 P （ n ）定义为 a _n =2 ⁿ +1。我们的目标是证明对于任意的 n ≥1， P （ n ）成立。 归纳基础 。

P (1)： a ₁ =2 ¹ +1=3

P (2)： a ₂ =2 ² +1=4+1=5

归纳假设 。对于某个 n ≥2，假设对于所有的 m ，1≤ m ≤ n ，有 P （ m ）成立，即 a _m =2 ^m +1。

归纳步骤 。证明 P ( n +1)，即 a _{n +1} =2 ^{n +1} +1成立。

下面举一个有关游戏策略的例子。在这个例子中，归纳不仅关系到归纳变量的前一个或两个值，还关系到所有更小的值。我们再次称玩家为Ali和Brad。

游戏中有一个巧克力棒，它是由 n × p 个“块”构成的网格状矩形（见图4.9）。我们使用术语“块”来表示单个1×1的网格方块。我们可以沿着巧克力棒长或宽的任何方向的接缝折断，将其分成两个较小的矩形。

从Ali开始。她可以水平或垂直地折断巧克力棒，从而得到两个分离的矩形。（玩家可以将巧克力棒旋转90°，所以“水平”和“垂直”只有在我们的插图中有意义。）Ali折断巧克力棒后，吃掉其中一个矩形，将另一个矩形递给Brad。Brad同样照做，把其中一个矩形递给Ali。Ali和Brad就这样一直做下去，直到某个人递给对方的矩形只有一块，接受的一方不能再做折断了，这个收到1×1矩形的玩家就失败了。

玩家获胜的最佳策略是什么呢？

让我们从玩家Ali的角度来看这个游戏，并用游戏结果来回溯过程。

Ali的目的是递给Brad一个1×1的矩形。如果开始的情况就是一个1×1的矩形（ n = p =1），那么她将失败。如果开始的情况是一个1× p 的矩形（任意的 p >1），那么她可以折断 p -1块，把剩下的一块递给Brad，Ali获胜。因此，1×1矩形对于任何持有它的人来说都是一个输掉游戏的情况，但是1× p （或者 p ×1）的矩形却是一个获胜的情况，其中 p >1（见图4.10）。

如果开始的情况是一个2×2矩形，那么，Ali可以用两种方式折断它。但无论选择哪种方式，她都会递给Brad一个2×1的矩形（或1×2的矩形，它们是等同的）。此时，Brad具有一个获胜的对策，即Brad可以采用与Ali面对一个1× p 的矩形时同样的对策。因此，如果开始的情况是一个2×2的矩形，Ali就无法获胜（见图4.11），那么2×2矩形对任何人来说都是一个输掉游戏的情况。

如果开始的情况是一个3×3矩形会怎样呢？Ali有多个选择：要么给Brad一个2×3或3×2的矩形（这两个效果是一样的），要么给Brad一个1×3或3×1的矩形（这两个效果也是一样的）。无论Ali以哪种方式折断3×3的巧克力棒，Brad都可以找到一种方法返给Ali一个更小的矩形（见图4.12），并且我们知道，如果Ali收到的是1×1或2×2的矩形，那么她都必输无疑。

因此，我们推测：如果先手玩家开始的情况不是正方形，那么他就有获胜的对策；而后手玩家只有在先手玩家开始的情况是正方形时，才有获胜的对策。

例4.3 从一个长宽不相等的 n × p 矩形（在不失一般性的情况下，设 p > n ）开始的玩家具有获胜的对策：折断 n ×（ p - n ）块，然后递给对手一个 n × n 矩形。从一个 n × n 矩形开始的玩家（对手使用了上述对策）将无法获胜。

解 ：设矩形的尺寸为 n × p ，其中 p ≥ n 。对较小维度的 n （ p 等于 n 除外）进行归纳证明。像往常一样，从Ali开始。

归纳基础 。 n ₀ =1。如果 p =1，那么Ali拿到的是一个1×1矩形，Ali失败。如果 p >1，那么Ali可以折断 p -1块[1×（ p -1）矩形]，并将单独一块递给Brad。则Brad失败，Ali获胜。

归纳假设 。对于某个 n ≥1，假设对于所有的 m ≤ n ，当 p > m 时，如果玩家的开始情况是一个 m × p 矩形，则具有获胜的对策，即折断一个 m ×（ p - m ）矩形，并将 m × m 矩形递给对手。如果玩家的开始情况是一个 m × m 矩形（对手使用了上述策略），则无法获胜。

归纳步骤 。假设Ali的开始情况是一个（ n +1）× p 矩形，其中 p ≥ n +1≥2。如果 p = n +1，则Ali失败：无论她如何折断巧克力棒，都只能递给Brad一个（ n +1）× m 矩形，其中 m < n +1。也就是说， m ≤ n ，但根据 归纳假设 ，Brad开始的情况是两个维度不相同且较小的维度小于或等于 n 的矩形，他有一个获胜的对策。此外，如果 p > n +1，那么Ali可以折掉一个（ n +1）×（ p -（ n +1））矩形，并交给Brad一个（ n +1）×（ n +1）矩形，这对Brad来说是无法获胜的情况，与Ali所遇到的情况（ p = n +1）完全相同。■

注意在这个证明中使用强归纳法最重要的部分是：当玩家有一个 n × p 的矩形，其中 p ≥ n ，那么该玩家可以向对手返回一个 m 维度的矩形（任意的 m 小于或等于 n ）。

在前面的示例中，证明 P （ n ）为真，我们的 归纳基础 是从 n ₀ =0或者 n ₀ =1开始的。有时，有些谓词对于有限数量的某些 n 值不为真，那么我们就证明它对于“足够大”的值是真的。也就是说，存在某些 n ₀ ，使得当 n < n ₀ 时， P （ n ）可能为假，但对于任意的 n ≥ n ₀ 都为真。在这些情况下，我们把 n ₀ 作为 归纳基础 的开始值（要特别当心：我们的 归纳步骤 不依赖于任何使 P （ n ）为假的较小的 n 值）。

例4.4 一套量杯包括量度为4杯、9杯、11杯和14杯的量杯各一个。证明这套量杯可用于测量大于或等于11杯的任何杯数。

解 ：要证明的命题泛化形式为 P （ n ）对于任意的 n ≥ n ₀ =11都成立。

归纳基础 。从11杯开始列举前几杯的情况。（重要的是，我们需要忽略任何小于11杯的情况，因为无法用给定的杯子测量10杯）。因为有一个11杯的量杯，所以我们使用一次就可以测量出11杯。我们可以三次使用4杯测量出12杯。对于13，我们可以使用4杯和9杯的组合。对于14杯，我们可以使用14杯。因此，如果我们假设谓词 P （ n ）表示“可以使用套杯的任意组合测量出 n 杯来”，那么我们已经确定了 P （11）、 P （12）、 P （13）和 P （14）都为真的四个 归纳基础 。

归纳假设 。对于任意的 n ≥ n ₁ =14，有 P （ m ）成立，其中 n ₀ ≤ m ≤ n 。

归纳步骤 。在假设 P （ m ）对 n ₀ 等于11到 n 之间（包括 n ）的所有 m 均为真的前提下证明 P （ n +1）：由于 n +1≥15，我们可以应用 归纳假设 测量（ n +1）-4杯，因为（ n +1）-4大于或等于11，这是已经证明的情况。我们可以用测量（ n +1）-4杯再加上一个4杯来测量（ n +1）杯。■

尽管我们给出的强归纳法好像是全新的、比基本数学归纳法更具通用性的方法，但实际上并非如此。事实上，能用强归纳法证明的任何命题，也都可以用基本归纳法来证明，或许不够巧妙（见习题4.6）。

由于强归纳法不是新的数学原理，只是更便利了，所以当我们说到归纳法时，不会严格地区分使用的是基本归纳法还是强归纳法。

数学归纳法还有另外一种看起来根本不像归纳法的版本。

良序原理 ： 任何非负整数的非空集合都有一个最小的元素 。

这个论断看起来很明显。如果 S 是一个大于或等于0的整数集合，并且 S 至少包含一个元素，那么其中之一必须是最小的。从数学基础的角度来看，这个原理也需要证明。实际上它与数学归纳法是等价的。证明两者之中的任何一个都需要深入探讨“假设”这一元数学问题，如果不按照这些原则，不难证明上述两个原理（数学归纳法与良序原理）之间的相互蕴含关系（习题4.8）。

借助于良序原理，我们可以证明定理1.5——算术基本定理，即每个大于1的整数 n 有唯一的质分解式。

证明 ：对 n 做数学归纳。

归纳基础 。 n ₀ =2。显然2=2 ¹ ，并且没有其他指数为正的质数的乘积可以等于2。

归纳假设 。对于某个 n ≥2，假设对于每个 m （2≤ m ≤ n ）有一个唯一的质分解式。

归纳步骤 。现在考虑 n +1的情况。如果 n +1是质数，那么 n +1=（ n +1） ¹ 是 n +1的唯一质分解式。如果 n +1不是质数，那么设 S 是其所有大于1的因子的集合。根据良序原理， S 有一个最小的元素 p ，它必为质数，否则 p 的任何因子都是 n +1的比 p 更小的因子。设 q =（ n +1）/ p ，那么 q ≤ n （实际上， q < n ），因此根据 归纳假设 ， q 具有唯一的质分解式：

p 要么是 p ₁ ，要么是小于 p ₁ 的质数，我们可以称之为 p ₀ 。在第一种情况下，有

在第二种情况下，有

我们将其作为一个练习：证明任何数不存在一个以上的质分解式（见习题4.7）。■

本章小结

• 强归纳法与基本归纳法有两方面不同：

1. 归纳基础 可以是多个值，要证明谓词对从 n ₀ 到 n ₁ （在基本归纳法中只有一个值 n ₀ ）的所有值都成立。

2. 归纳假设 断言谓词对于小于某个确定的 n 的所有值都成立，其中 n ≥ n ₁ （而在基本归纳法中的 归纳假设 谓词仅对 n ≥ n ₀ 成立）。

• 归纳证明也适用于命题在有限多个情况下为假的情况。在这种情况下，选择的最小归纳基础 n ₀ 使得 P （ n ）为真，并且对于任意的 n ≥ n ₀ ， P （ n ）都为真。 归纳步骤 不依赖于任何命题为假的情况。

• 强归纳法比基本归纳法更加便利：能用强归纳法证明的任何东西也可以采用基本归纳法证明。

• 良序原理（即任何非负整数的非空集合都有一个最小的元素）等价于归纳法。

习题

4.1 设 a ₁ =0、 a ₂ =6、 a ₃ =9。对于 n >3, a _n = a _{n -1} + a _{n -3} 。证明对于所有 n ， a _n 可被3整除。

4.2 证明对于所有的 n ≥8，存在整数 a 和 b ，使得 n =3 a +5 b ，即 n 是多个3与多个5的和。

4.3 证明对于任意的 n >1，可以使用由三个正方形组成的L形砖片（见图4.13）平铺一个2 ⁿ ×2 ⁿ 正方形，只留角上有一个空白的正方形（见图4.14）。其中，L形砖片可以以任何方向旋转和使用。

4.4 假设已知实数 x ，使得 是整数。应用强归纳法证明：对于任意整数 ，都有 是整数。

提示 ：将乘积 展开找到一个有助于归纳的等式。

4.5 设 S 是一个数列 a ₁ , a ₂ , a ₃ ,…，其中 a ₁ =1、 a ₂ =2、 a ₃ =3，并且对于任意的 n ≥4，有 a _n = a _{n -1} + a _{n -2} + a _{n -3} 。应用强归纳法证明：对于任意的正整数 n ，有 a _n <2 ⁿ 。

4.6 证明：能够用强归纳法证明的任意命题都可以用基本归纳法证明。

4.7 证明：质分解式是唯一的，即如果有

其中 p _i 、 r _i 都是递增的质数，且所有指数 e _i 、 f _i 都是正整数，那么存在 k = l ，对于每个 i ，有 p _i = r _i 、 e _i = f _i 。

4.8 （a）证明：数学归纳法蕴含良序原理。提示：对非负整数的非空集合的大小进行归纳，假设“如果一个集合非空，那么就能找到它的一个成员”。

（b）证明：良序原理蕴含数学归纳法。 提示 ：假设 P （ n ₀ ）为真，并且对于每一个 n ，有“如果 P （ n ）为真，则 P （ n +1）为真”。由于某些原因， P （ n ）不是对于所有的 n ≥ n ₀ 都为真。关于非负整数集合中 P 为假的原因。

4.9 应用算术基本定理证明中给出的方法，找到100的质分解式。展示每个阶段的 S 、 p 和 q 的值。

4.10 假设你能买到的邮票只有2美分和3美分两种面值。证明只要 n ≥2， n 美分的邮费最多使用 张邮票。 vW9KNV+FPu+dhjzwSnUR9xyOaEuN4ECICsBKRYK6q41UlcxXMHpW6uS/g3vulBeL