直接证明 | 杨星宇

直接证明从题设出发，通过定义和有依据的推导得到结论。难点往往不是计算，而是决定该展开哪个定义，以及结论需要什么形式。本篇先训练这种习惯，再进入分类证明、间接证明和数学归纳法。

把命题翻译成证明任务

要证明每个满足 $P$ 的对象都满足 $Q$ ，就任取论域中的对象，假设 $P$ ，再推出 $Q$ 。“任取”意味着只能使用论域和题设提供的条件，不能借助某个具体数值独有的性质。这样得到的结论才适用于全部允许的对象。

动笔时可以依次确认论域、展开条件、查看目标的定义，再寻找二者之间的连接。MIT 的证明入门讲义也从明确假设和推导依据的角度组织证明 [1]。

目标	证明完成时需要交代什么
$n$ 是偶数	找到整数 $m$ ，使 $n=2m$
$n$ 是奇数	找到整数 $m$ ，使 $n=2m+1$
$d\mid n$	找到整数 $m$ ，使 $n=dm$
$x\in\mathbb Q$	找到整数 $a,b$ ，其中 $b\ne0$ ，使 $x=a/b$
$x\le y$	给出比较依据，例如证明 $y-x\ge0$

存在性命题中，构造候选对象只是第一步，还要验证它属于指定论域并满足要求。“当且仅当”命题则需要两个方向；建立一个方向的推导链，不会自动证明逆向也成立。

完整例子：把结论需要的形式整理出来

命题奇数的平方仍是奇数

若整数 $n$ 是奇数，则 $n^2$ 是奇数。

条件给出了 $n$ 的表示，目标要求把 $n^2$ 写成“某个整数的两倍加一”。因此可以先展开平方，再把偶数部分收拢。

证明

任取奇整数 $n$ 。存在整数 $k$ ，使 $n=2k+1$ 。于是

\begin{aligned} n^2&=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}

$2k^2+2k$ 是整数，因此最后一式符合奇数的定义，故 $n^2$ 是奇数。

最后一句不能省掉：它解释了计算为什么完成了目标。这里也没有要求 $k$ 为正，同一推导同时覆盖负奇数和 $n=1$ 等情形。

不同对象要使用独立的见证

命题两个有理数之和仍是有理数

若 $x,y\in\mathbb Q$ ，则 $x+y\in\mathbb Q$ 。

证明

写成 $x=a/b$ 、 $y=c/d$ ，其中 $a,b,c,d$ 都是整数，且 $b,d\ne0$ 。那么

x+y=\frac{ad+bc}{bd}.

分子、分母都是整数，且 $bd\ne0$ ，所以这个和按定义是有理数。

不能没有依据地让 $x,y$ 共用同一个分子或分母。同理，两个偶整数应先分别写成 $2k$ 和 $2m$ ，而不是都写成 $2k$ 。重复使用同一个见证，可能把关于任意两个对象的命题偷偷缩成只讨论二者相等的情形。

可以倒着找思路，但要正当地给出依据

构思证明时，可以从目标反问“证明什么就足够了”。正式写作时，还需要从真实题设建立这些充分条件。若把待证等式当作已知开始计算，却没有说明各步可逆、终点独立成立，就可能形成循环论证。

例观察差值，发现平方

对实数 $a,b$ ，证明 $a^2+b^2\ge2ab$ 。两边作差会提示

a^2+b^2-2ab=(a-b)^2.

正式证明可以从已知事实 $(a-b)^2\ge0$ 出发，展开后移项。等号恰在 $a=b$ 时成立。平方形式同时解释了不等式和等号条件。

每一步运算也有适用条件。除以 $a-b$ 之前要知道 $a\ne b$ ；给不等式乘上符号未知的式子，可能需要改变不等号方向；解方程时平方两边还可能引入额外候选解。这些条件要在证明里处理，不能藏在计算中。

练习

打开解析之前，先写出目标所需的表示。前三题练习定义与整除性，后两题把同一思路用于构造见证和证明等价。

练习偶数的平方

证明偶整数的平方仍是偶数。

查看解析

解

设 $n=2k$ ，其中 $k\in\mathbb Z$ ，则 $n^2=4k^2=2(2k^2)$ 。 $2k^2$ 是整数，所以 $n^2$ 是偶数。只看到一个因子 $2$ 还不够，说明另一个因子是整数才完成了定义上的要求。

练习两个偶数之和

证明任意两个偶整数之和仍是偶数。解释为什么不能把两个数都用同一个见证表示。

查看解析

解

分别设 $a=2k$ 、 $b=2m$ ，其中 $k,m$ 是独立选取的整数。那么 $a+b=2(k+m)$ ，而 $k+m$ 为整数。若都写成 $2k$ ，就只证明了 $a=b$ 这一受限情形。

练习说明所用依据的整除证明

证明对每个整数 $n$ ，都有 $3\mid n^3+2n$ 。可以使用“三个连续整数中至少一个能被 $3$ 整除”这一事实，下一篇会用余数说明它。

查看解析

解

将表达式改写为

n^3+2n=(n-1)n(n+1)+3n.

第一个乘积中有一个因子能被 $3$ 整除，所以乘积可写成 $3m$ ，其中 $m$ 是整数。整个式子因此等于 $3(m+n)$ 。这里不能要求 $m$ 为正： $n=1$ 时乘积为 $0$ 。同一证明也覆盖零和负整数。

练习构造并验证见证

给定有理数 $a<b$ ，构造一个严格位于二者之间的有理数，并证明它满足全部条件。

查看解析

解

取 $c=(a+b)/2$ 。有理数对加法和乘法封闭，所以 $c$ 是有理数。并且

c-a=\frac{b-a}{2}>0, \qquad b-c=\frac{b-a}{2}>0.

故 $a<c<b$ 。验证有理性和两条严格不等式，才把候选对象变成了存在性证明。

练习两个方向都要证明

对整数 $n$ ，证明 $n$ 是奇数当且仅当 $n+1$ 是偶数。

查看解析

解

若 $n=2k+1$ ，其中 $k\in\mathbb Z$ ，则 $n+1=2(k+1)$ 为偶数。反过来，若 $n+1=2m$ ，其中 $m\in\mathbb Z$ ，则 $n=2m-1=2(m-1)+1$ 为奇数。两个方向分别从各自的条件出发，现在才建立了充要关系。

什么时候考虑换方法

条件给出显式表示或熟悉的不等式时，可以先试直接证明。若定义随奇偶、正负或余数改变，分类证明能让每个分支使用合适的形式；若结论的否定提供了更有用的信息，可以考虑间接证明。方法负责组织推理，不能替代对各步依据的检查。

参考文献

[1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩

把命题翻译成证明任务

完整例子：把结论需要的形式整理出来

不同对象要使用独立的见证

可以倒着找思路，但要正当地给出依据

练习

什么时候考虑换方法

参考文献

评论