A.1　弱归纳法Weak induction

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

（本附录开篇语）本附录意在为从未见过用数学归纳法写证明的学生提供应急帮助。这种方法基于一个简单的想法，但要成功运用它需要练习。因此，在读完我们对该方法的快速回顾之后，读者应当查阅任何一本关于“向高等数学过渡”的教材，例如 [78]，以获得对该方法更详尽的处理；或查阅 [12]，其中有一章专门讲该方法在组合学中的应用。

如果一个陈述今天为真，并且“它在某一天为真”这一事实能推出“它在第二天也为真”这一事实，那么我们就可以断定：从今天起，这个陈述每一天都为真。这方面的一个例子是陈述“2004 赛季的橄榄球赛季已经结束”。

这个想法正是一件非常强大、且极常被使用的证明数学陈述的工具——即数学归纳法——的核心。把上面这个想法直截了当地搬到更数学化的语境中，便是如下表述：设有一个涉及变量 \(n\) 的陈述，它在 \(n=1\) 时为真；并且，由“它在 \(n=k\) 时为真”这一事实，能推出“它在 \(n=k+1\) 时也为真”这一事实。那么，这个陈述对所有正整数 \(n\) 都为真。

在实际操作中，证明陈述在 \(n=1\) 时为真通常很容易（这叫初始步骤，initial step）；但要证明“陈述在 \(n=k\) 时为真”能推出“它在 \(n=k+1\) 时也为真”，则要稍难一些。一旦我们成功证明了这两条“局部的”陈述，归纳法就能保证：原来那条“全局的”陈述对所有正整数 \(n\) 都为真。

下面用一个具体的求和公式演示整套方法。

1. 初始步骤（\(n=1\)）。 左边只有 \(i=1\) 一项：\(\sum_{i=1}^{1} i(i-1)=1\cdot(1-1)=0\)。右边为 \(\dfrac{(1+1)\cdot 1\cdot(1-1)}{3}=\dfrac{2\cdot1\cdot0}{3}=0\)。两边都等于 \(0\)，故 \(n=1\) 时 (A.1) 成立。
2. 归纳假设。 设 (A.1) 对 \(n=k\) 成立，即 \[\sum_{i=1}^{k} i(i-1)=\frac{(k+1)\,k\,(k-1)}{3}.\]
3. 归纳步骤（推出 \(n=k+1\)）。 把 \(n=k+1\) 的和拆成“前 \(k\) 项”加“第 \(k+1\) 项”，前 \(k\) 项用归纳假设替换： \[\sum_{i=1}^{k+1} i(i-1)=\underbrace{\sum_{i=1}^{k} i(i-1)}_{\text{用归纳假设}}+(k+1)\,k=\frac{(k+1)k(k-1)}{3}+(k+1)k.\]
4. 提取公因式并通分。 两项都含公因式 \((k+1)k\)： \[\frac{(k+1)k(k-1)}{3}+(k+1)k=(k+1)k\left[\frac{k-1}{3}+1\right]=(k+1)k\cdot\frac{(k-1)+3}{3}=(k+1)k\cdot\frac{k+2}{3}.\]
5. 对照目标式。 把上式整理为 \(\dfrac{(k+2)(k+1)k}{3}\)。而 (A.1) 在 \(n=k+1\) 时的右边为 \[\frac{((k+1)+1)\,(k+1)\,((k+1)-1)}{3}=\frac{(k+2)(k+1)k}{3},\] 两者完全一致。故 (A.1) 对 \(n=k+1\) 也成立。♦

既然初始步骤与归纳步骤都已完成，由数学归纳法即知 (A.1) 对所有正整数 \(n\) 成立。

返回 全书目录