7. 数学证明技巧¶

7.1. 数学证明技巧¶

解决任何问题都有两个截然不同的部分：探究和论证。学生在教科书和课堂上看到的往往只有论证，对此他们太过习以为常。但要想在学业上（以及毕业后的生活中）取得成功，一个人必须同时擅长这两者，并理解这一过程的这两个阶段之间的差异。要解决问题，你必须成功地探究。这意味着要投入问题之中，一直钻研到找到解法为止。然后，为了向你的"客户"给出答案（无论这个"客户"是批改作业或考试的老师，还是你要向其提交书面报告的老板），你需要能够以清晰而简洁的方式把解法表达出来，也就是进行论证。论证阶段需要良好的技术写作能力—即做出清晰、合乎逻辑的论证的能力。

熟悉标准的证明技巧对你有帮助。知道如何写出好的证明在许多方面都有益处。第一，它能厘清你的思维过程，进而使你的解释更清晰。第二，如果你采用某种标准证明结构，比如反证法或归纳证明，那么你和读者都基于对该结构的共同理解来工作。这能降低读者理解你证明的难度，因为读者不必从零开始解读你论证的结构。

本节简要介绍三种常用的证明技巧：

演绎，或称直接证明；
反证法，以及
数学归纳证明。

7.1.1. 直接证明¶

一般来说，直接证明不过是一种"逻辑解释"。直接证明有时也称为演绎论证。它无非是依据逻辑进行的论证。

许多直接证明用英语写成，其中使用"如果……那么"之类的词。在这种情况下，像 \(P \Rightarrow Q\) 这样的逻辑记号常常有助于表达证明。即使我们不想使用符号逻辑记号，也仍然可以利用逻辑的基本定理来组织论证。例如，如果要证明 \(P\) 和 \(Q\) 等价，我们可以先证明 \(P \Rightarrow Q\) ，再证明 \(Q \Rightarrow P\) 。

在一些领域中，证明本质上是从起始状态到结束状态的一系列状态变化。形式谓词逻辑可以这样来看：用各种"逻辑规则"从一个公式作出变化，或把几个公式组合成一个新公式，一步步走向目标。在入门的微积分课程中求解积分问题所用的符号演算，在精神上与之相似，高中几何证明也是如此。

7.1.2. 反证法¶

要证伪一个定理或命题，最简单的方法是为该定理找一个反例。遗憾的是，无论有多少支持某定理的例子，都不足以证明该定理正确。不过，有一种与用反例证伪大致相似的方法，称为反证法。要用反证法证明一个定理，我们首先假设该定理为假。然后，我们找出由这个假设导致的一个逻辑矛盾。如果用来找出矛盾所依据的逻辑是正确的，那么解决这个矛盾的唯一办法，就是承认"该定理为假"这个假设必定不成立。也就是说，我们得出结论：该定理必定为真。

一种相关的证明技巧是证明逆否命题。我们可以通过证明 \((\mathrm{not}\ Q) \Rightarrow (\mathrm{not}\ P)\) 来证明 \(P \Rightarrow Q\) 。这种技巧之所以有效，是因为这两个逻辑命题的真值表相同。

7.1.3. 数学归纳证明¶

数学归纳法可以用来证明各种各样的定理。归纳法还提供了一种思考算法设计的有用方式，因为它鼓励你从简单的子问题出发，逐步构建来解决问题。归纳法有助于证明一个递归函数能产生正确的结果。理解递归是通向理解归纳法的一大步，反之亦然，因为二者本质上遵循相同的过程。

在算法分析的语境中，数学归纳法最重要的用途之一，是作为一种检验假设的方法。当我们为求和或递推关系寻找闭式解时，可能会先猜测，或者以其他方式获得证据，表明某个特定公式就是正确的解。如果该公式确实正确，用归纳证明来证明这一点往往很容易。

设 Thrm 是待证明的定理，并用正整数参数 \(n\) 来表示 Thrm 。数学归纳法指出，如果下面两个条件成立，则 Thrm 对参数 \(n\) 的任意取值都成立（ \(n \geq c\) ，其中 c 是某个常数）：

基本情况： Thrm 对 \(n = c\) 成立，并且
归纳步骤：如果 Thrm 对 \(n - 1\) 成立，那么 Thrm 对 \(n\) 成立。

证明基本情况通常很容易，一般只需把诸如 1 这样的较小取值代入定理中的 \(n\) ，再按需运用简单的代数或逻辑来验证定理。证明归纳步骤有时容易，有时困难。归纳步骤的一种替代表述称为强归纳法。强归纳法的归纳步骤是：

2a. 归纳步骤 ：如果 Thrm 对所有 \(k, c \leq k < n\) 都成立，那么 Thrm 对 \(n\) 成立。

证明归纳步骤的任一种表述（并结合验证基本情况），都能得到令人满意的数学归纳证明。

构成归纳证明的这两个条件结合起来，说明 Thrm 对 \(n=2\) 成立，这是 Thrm 对 \(n=1\) 成立这一事实的延伸。这一事实再结合条件 (2) 或 (2a)，表明 Thrm 对 \(n=3\) 也成立，依此类推。因此，一旦这两个条件得到证明， Thrm 就对 \(n\) 的所有取值（大于基本情况的取值）都成立。

数学归纳法之所以如此强大（对大多数人来说一开始又如此神秘），是因为我们可以利用" Thrm 对所有小于 \(n\) 的值都成立"这一假设作为工具，来帮助我们证明 Thrm 对 \(n\) 成立。这称为归纳假设。有了这个假设可用，归纳步骤就比直接处理原定理本身更容易证明。能够依赖归纳假设，就提供了额外的信息，让我们可以用来处理问题。

递归和归纳有许多相似之处。二者都锚定在一个或多个基本情况上。递归函数依赖调用自身的能力，来求得问题更小实例的答案。同样，归纳证明依赖归纳假设的真实性来证明定理。归纳假设并非凭空而来。它成立当且仅当定理本身成立，因此在证明的语境中是可靠的。利用归纳假设来完成工作，与利用递归调用来完成工作完全相同。

Example 3.7.3

下面是一个数学归纳证明的样例。把前 \(n\) 个正整数之和记为 \(\mathbf{S}(n)\) 。

定理： \(\mathbf{S}(n) = \frac{n(n+1)}{2}\) 。

证明：证明采用数学归纳法。

检查基本情况 。对 \(n = 1\) ，验证 \(\mathbf{S}(1) = 1(1+1)/2\) 。 \(\mathbf{S}(1)\) 就是第一个正整数的和，即 1。因为 \(\frac{1(1+1)}{2} = 1\) ，所以该公式在基本情况下是正确的。
陈述归纳假设 。归纳假设是

\[\mathbf{S}(n-1) = \sum_{i=1}^{n-1} i = \frac{(n-1)((n-1)+1)}{2} = \frac{(n-1)(n)}{2}.\]
利用归纳假设中针对 \(n-1\) 的假设来证明结果对 \(n\) 成立。归纳假设断言 \(\mathbf{S}(n-1) = \frac{(n-1)(n)}{2}\) ，并且由于 \(\mathbf{S}(n) = \mathbf{S}(n-1) + n\) ，我们可以代入 \(\mathbf{S}(n-1)\) 得到

\[\begin{split}\sum_{i=1}^n i &=& \left(\sum_{i=1}^{n-1} i\right) + n = \frac{(n-1)(n)}{2} + n\\ &=&\frac{n^2 - n + 2n}{2} = \frac{n(n+1)}{2}.\end{split}\]

因此，由数学归纳法，

\[\mathbf{S}(n) = \sum_{i=1}^n i = n(n+1)/2.\]

请仔细注意这个例子中发生的事情。首先，我们把 \(\mathbf{S}(n)\) 用问题的一个更小实例来表示： \(\mathbf{S}(n) = \mathbf{S}(n-1) + n\) 。这很重要，因为一旦 \(\mathbf{S}(n-1)\) 进入视野，我们就可以用归纳假设把 \(\mathbf{S}(n-1)\) 替换为 \((n-1)(n)/2\) 。从这里出发，只需简单的代数就能证明 \(\mathbf{S}(n-1) + n\) 等于原定理的右端。

我们可以把例题 3.7.3 中的归纳证明与例题 3.7.1 中的直接证明相比较。不同的人可能觉得其中一个比另一个更容易理解，但直接证明版本的作者肯定必须发现一个该问题特有的洞见，而这个洞见在证明其他求和时可能并无帮助或并不相关。

Example 3.7.4

下面是另一个简单的归纳证明，它说明了如何为归纳选择合适的变量。我们希望用归纳法证明：前 \(n\) 个正奇数之和为 \(n^2\) 。首先，我们需要一种方式来描述第 \(n\) 个奇数，它无非就是 \(2n - 1\) 。这也让我们可以把该定理写成求和的形式。

定理： \(\sum_{i=1}^n (2i - 1) = n^2\) 。

证明： \(n = 1\) 的基本情况给出 \(1 = 1^2\) ，这是成立的。归纳假设是

\[\sum_{i=1}^{n-1} (2i - 1) = (n-1)^2.\]

现在我们用归纳假设来证明定理对 \(n\) 成立。前 \(n\) 个奇数之和，就是前 \(n-1\) 个奇数之和再加上第 \(n\) 个奇数。在下面的第二行中，我们将用归纳假设把部分和（第一行中用方括号标出）替换为它的闭式解。之后，代数就能完成剩下的工作。

\[\begin{split}\sum_{i=1}^n (2i - 1) &=& \left[ \sum_{i=1}^{n-1} (2i - 1) \right] + 2n - 1\\ &=& [(n-1)^2] + 2n - 1\\ &=& n^2 - 2n + 1 + 2n - 1\\ &=& n^2.\end{split}\]

因此，由数学归纳法，

\[\sum_{i=1}^n (2i - 1) = n^2.\]

Example 3.7.6

这个例子使用归纳法，但不涉及求和或其他方程。它还说明了基本情况的更灵活用法。

定理：用 2 分和 5 分邮票可以凑出任意邮资（对 \(\geq 4\) 的值）。

证明：该定理针对 \(\geq 4\) 的值来定义问题，因为对值 1 和 3 它不成立。以 4 为基本情况，4 分可以用两张 2 分邮票凑出。归纳假设是：值 \(n-1\) 可以由 2 分和 5 分邮票的某种组合凑出。现在我们用归纳假设来说明如何用 2 分和 5 分邮票得到值 \(n\) 。值 \(n-1\) 的构成要么包含一张 5 分邮票，要么不包含。如果包含，就用三张 2 分邮票替换一张 5 分邮票。如果不包含，那么其构成必定至少包含两张 2 分邮票（因为它的值至少为 4，且只含 2 分邮票）。在这种情况下，用一张 5 分邮票替换其中两张 2 分邮票。无论哪种情况，我们现在都得到了由 2 分和 5 分邮票组成的值 n。因此，由数学归纳法，该定理正确。

我们的下一个数学归纳例子证明一个几何定理。它还说明了一种标准的归纳证明技巧：取 \(n\) 个对象，去掉某个对象，以便使用归纳假设。

把例题 3.7.8 中的证明与例题 3.7.6 中的证明相比较。对于例题 3.7.6 ，我们取一个规模为 \(n-1\) 的邮票集合（根据归纳假设，它必定具有所期望的性质），并由此"构造"出一个规模为 \(n\) 、具有所期望性质的集合。因此，我们证明了存在某个具有所期望性质、规模为 \(n\) 的邮票集合。

对于例题 3.7.8 ，我们必须证明任意 \(n\) 条直线的集合都具有所期望的性质。因此，我们的策略是取一个 任意的 \(n\) 条直线的集合，并"缩减"它，从而得到一个必定具有所期望性质的直线集合，因为它与归纳假设相符。从这里出发，我们只需证明，把原来的缩减过程反过来能保持所期望的性质。由于我们控制了缩减过程，我们也就控制了这一缩减的逆过程。

相比之下，考虑一下如果我们试图从规模为 \(n-1\) 的直线集合"构造"出规模为 \(n\) 的集合，需要做些什么。我们将很难证明所有可能的 \(n\) 条直线的集合都被我们的构造过程所覆盖。通过从一个任意的 \(n\) 条直线的集合缩减到更小的集合，我们避开了这个问题。

与"从 \(n-1\) 向上构造"相比，"从 \(n\) 缩减"这一思路的另一个优点在于：缩减更像我们编写递归函数时所做的。在递归中，我们自然会通过（递归地）在 \(n-1\) 上调用该函数来计算 \(n\) 的某个函数值，然后用结果计算 \(n\) 的值。

本节的最后一个例子展示了如何用归纳法证明一个递归函数能产生正确的结果。

Example 3.7.9

我们希望证明函数 fact 确实计算的是阶乘函数。这样的证明有两个截然不同的步骤。第一步是证明该函数总是会终止。第二步是证明该函数返回正确的值。

定理：函数 fact 对任意 \(n\) 值都会终止。

证明：对于基本情况，我们观察到只要 \(n \leq 0\) ， fact 就会直接终止。归纳假设是 fact 对 \(n-1\) 会终止。对于 \(n\) ，我们有两种可能。一种可能是 \(n \geq 12\) 。在这种情况下， fact 会直接终止，因为它无法通过断言测试。否则， fact 会递归调用 fact(n-1) 。根据归纳假设， fact(n-1) 必定会终止。

定理：函数 fact 对 0 到 12 范围内的任意值确实计算阶乘函数。

证明：为证明基本情况，观察到当 \(n=0\) 或 \(n=1\) 时， fact(n) 返回正确的值 1。归纳假设是 fact(n-1) 返回 (n-1)! 的正确值。对于合法范围内的任意值 n ， fact(n) 返回 \(n *\) fact(n-1) 。根据归纳假设， fact(n-1) \(= (n-1)!\) ，并且由于 \(n * (n-1)! = n!\) ，我们证明了 fact(n) 产生正确的结果。

我们可以用类似的过程证明许多递归程序是正确的。一般形式是：先证明基本情况执行正确，然后用归纳假设证明递归步骤也产生正确的结果。在此之前，我们必须证明该函数总是会终止，这也可以用归纳证明来完成。

CS415 数据结构与算法

Chapter 3 Mathematical Background