Bóna · 枚举与解析组合学导论 · 附录 附录：数学归纳法

A.2　强归纳法Strong induction

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

有时候，只知道一条命题“今天”成立，并不足以推断它“明天”仍然成立；有时我们需要知道这条命题“到今天为止的每一天”都成立，才允许我们作出这样的推断。类似地，有时我们需要知道一条命题对所有满足 \(k\le n\) 的值都成立，才能推断它对 \(n+1\) 也成立。如果情况确实如此，且该命题在 \(n=1\) 时成立，那么它必定对所有的 \(n\) 都成立。事实上，由它在 \(n=1\) 时成立，可推出它在 \(n=2\) 时成立，因为 \(1\) 是唯一一个小于 \(2\) 的正整数。接着，由于命题在 \(n=1\) 和 \(n=2\) 时都成立，它在 \(n=3\) 时成立；再由于它在 \(n=1\)、\(n=2\) 和 \(n=3\) 时都成立，它在 \(n=4\) 时成立；如此继续下去。

这种使用一个更强的归纳假设来对所有 \(n\) 证明命题的方法，称为强归纳法（method of strong induction）。

本节目标把“普通归纳法”升级成“强归纳法”：当证明 \(n+1\) 的情形时，普通归纳只允许借用紧挨着的前一项（\(n\) 成立），而强归纳允许同时借用前面所有项（\(1,2,\dots,n\) 全都成立）。当一个量是“由它前面全部的项一起决定”的时候，就必须用强归纳法。

普通归纳与强归纳的区别

两种方法的“起步”一模一样：都要先验证 \(n=1\)。区别只在“归纳步”里允许使用什么前提。

  1. 普通归纳的归纳假设：“命题对 \(n=k\) 成立”，只借用一项，用它去证 \(n=k+1\)。
  2. 强归纳的归纳假设：“命题对所有 \(k\le n\) 都成立”，可同时借用前面全部的项，用它们去证 \(n+1\)。
  3. 强归纳之所以照样有效，是因为这一长串推断可以从 \(n=1\) 逐格自动接力下去：\(\{1\}\Rightarrow 2\)，\(\{1,2\}\Rightarrow 3\)，\(\{1,2,3\}\Rightarrow 4\)，每一格都用上了它前面已经确立的全部结论。
n=1 起步已验证 {1} n=2 {1,2} n=3 {1,2,3} n=4 {1,2,3,4} … 所有 n
每个箭头上方花括号里列出的，是推出下一格时所用到的全部已知情形。普通归纳每次只用紧邻的一格，强归纳把前面整段都用上。

一个必须用强归纳的例子

例 A.2 设 \(a_0=1\)，并且当 \(n\ge 1\) 时令 \[\tag{A.4}a_n=\sum_{i=0}^{n-1}2a_i.\] 证明：对所有正整数 \(n\)，都有 \(a_n=2\cdot 3^{\,n-1}\)。
为什么这里非用强归纳不可看公式 (A.4)：\(a_n\) 是把它前面所有的项 \(a_0,a_1,\dots,a_{n-1}\) 各乘 \(2\) 再全部加起来得到的。要算 \(a_{n+1}\)，就要用到 \(a_0\) 到 \(a_n\) 全部的值——只知道紧挨着的 \(a_n\) 根本不够，所以必须采用“所有 \(k\le n\) 都成立”的强归纳假设。

先用几个具体数字感受一下这个数列，确认要证的公式确实对：

n 按 (A.4) 计算 结果 2·3ⁿ⁻¹ 0 a₀ = 1（初值） 1 — 1 2a₀ = 2·1 2 2·3⁰ = 2 2 2(a₀+a₁) = 2(1+2) 6 2·3¹ = 6 3 2(a₀+a₁+a₂) = 2(1+2+6) 18 2·3² = 18
前几项逐一吻合：\(a_1=2,\ a_2=6,\ a_3=18\)，都等于 \(2\cdot 3^{\,n-1}\)。这给了我们信心，下面用强归纳给出严格证明。
证明.
  1. 初始步. 当 \(n=1\) 时，公式 (A.4) 给出 \(a_1=2\cdot a_0=2\)，与待证公式 \(2\cdot 3^{\,1-1}=2\cdot 3^0=2\) 一致。
  2. 归纳步. 设命题对所有 \(k\le n\) 都成立（这就是强归纳假设：\(a_k=2\cdot 3^{\,k-1}\) 对 \(1\le k\le n\) 全部成立）。那么由 (A.4) 计算 \(a_{n+1}\)： \[ \begin{aligned} a_{n+1}&=\sum_{k=0}^{n}2a_k\\ &=2\Big(1+2\cdot\sum_{k=1}^{n}3^{\,k-1}\Big)\\ &=2+4\cdot\sum_{k=1}^{n}3^{\,k-1}\\ &=2+4\cdot\frac{3^{\,n}-1}{2}\\ &=2\cdot 3^{\,n}. \end{aligned} \] 于是命题对 \(k=n+1\) 也成立。
因此，由强归纳法，命题对所有正整数 \(n\) 都成立。♦

把上面那串等式一行一行讲清楚“每一步为什么这么写”：

  1. 第一行：直接抄定义 (A.4)，注意求和上限从 \(n-1\) 变成 \(n\)（因为现在算的是 \(a_{n+1}\)）。
  2. 第二行：把 \(k=0\) 这一项单独拎出来——\(2a_0=2\cdot 1\)；其余 \(k=1,\dots,n\) 这些项，每一个都用强归纳假设替换成 \(a_k=2\cdot 3^{\,k-1}\)，于是 \(2a_k=2\cdot 2\cdot 3^{\,k-1}\)，提出公因子后写成 \(2\big(1+2\sum_{k=1}^{n}3^{\,k-1}\big)\)。这一步正是“非强归纳不可”的地方：它一次性用掉了 \(a_1\) 到 \(a_n\) 的全部结论。
  3. 第三行：把外层的 \(2\) 乘进括号，得到 \(2+4\sum_{k=1}^{n}3^{\,k-1}\)。
  4. 第四行：求和 \(\sum_{k=1}^{n}3^{\,k-1}=3^0+3^1+\dots+3^{\,n-1}\) 是首项 \(1\)、公比 \(3\) 的等比数列，其和等于 \(\dfrac{3^{\,n}-1}{3-1}=\dfrac{3^{\,n}-1}{2}\)。
  5. 第五行：代入并化简 \(2+4\cdot\dfrac{3^{\,n}-1}{2}=2+2(3^{\,n}-1)=2+2\cdot 3^{\,n}-2=2\cdot 3^{\,n}\)。
  6. 最后核对：待证公式在 \(n+1\) 处应给出 \(2\cdot 3^{\,(n+1)-1}=2\cdot 3^{\,n}\)，与算得的 \(a_{n+1}\) 完全吻合。证毕。
用 n=3 实地验算归纳步 取 \(n=3\)，看看归纳步是怎样推出 \(a_4\) 的。强归纳假设此时是 \(a_1=2,\ a_2=6,\ a_3=18\)（前面全部已知）。于是 \[a_4=2(a_0+a_1+a_2+a_3)=2(1+2+6+18)=2\cdot 27=54=2\cdot 3^3.\] 而公式预测 \(2\cdot 3^{\,4-1}=2\cdot 27=54\)，一致。可见推出 \(a_4\) 时，\(a_1,a_2,a_3\) 一个都不能少。

归纳法的种种变体

归纳法有许多变体。\(n\) 允许取的最小值可以不是 \(1\)，这时初始步需要作相应的修改；也可以有多个变量。如果读者此前未做过归纳证明，鼓励读者查阅本附录开头提到的参考文献，并多加练习。

即时自测
  1. 仍用例 A.2 的数列，直接按定义 (A.4) 算出 \(a_5\)（先用 \(a_0,\dots,a_4\) 求和），再用公式 \(2\cdot 3^{\,n-1}\) 验证两者相等。
  2. 在例 A.2 的证明里，如果只假设“命题对 \(n=k\) 成立”（普通归纳的单项假设），第二行的那一步还能照样写出吗？说明为什么这正是必须用强归纳的原因。
  3. 设 \(b_1=1\)，且当 \(n\ge 2\) 时 \(b_n=\sum_{i=1}^{n-1}b_i\)。先算出 \(b_2,b_3,b_4,b_5\)，再猜出一个关于 \(b_n\)（\(n\ge 2\)）的封闭公式，并用强归纳法证明它。

返回 全书目录