强归纳、良序原理与递归定义

上一章里，普通归纳的节奏很整齐：先站稳起点，再把 $P(n)$ 推到 $P(n+1)$。可离散数学里的对象不总排成一条只看前一步的队伍。一棵树会分成左右两棵子树，一个合数会拆成两个更小因子，斐波那契数的下一项要同时回看前两项。此时如果归纳假设只给我们 $P(n-1)$，手里的材料就不够顺手了。

这一章要做的，是把“向更小对象追溯”这件事讲清楚。强归纳允许我们调用全部更小情形；良序原理把“若真有失败者，就取最小的那个”变成严密论证；递归定义则从相反方向出发，说明复杂对象怎样由简单对象一步步造出来。三条线最后会在结构归纳和递归过程里汇合。

普通归纳什么时候显得不够用

先把一句容易误解的话说准：强归纳在逻辑能力上并不比普通归纳更强。凡是强归纳能证明的自然数命题，都能改写成普通归纳证明。我们说“普通归纳不够用”，通常是指只假设紧邻前件 $P(n-1)$ 的那种直接写法，拿不到当前证明真正需要的较小情形。

例如，要证明整数 $84$ 能写成素数的乘积，最自然的第一步不是研究 $83$，而是把 $84$ 拆成 $6\times14$。随后我们需要的是“$6$ 可以分解”和“$14$ 可以分解”。这两个下标都比 $84$ 小，却都不是 $$。如果归纳假设只交给我们 ，它与眼前的分解结构根本接不上。

强归纳正是把假设范围放宽。要证明对所有 $n\ge n_0$，命题 $P(n)$ 成立，可以使用下面的形式：

并且对每个 $n>n_0$，证明

于是得到

这里最要紧的边界是 $k<n$。归纳步骤允许假设的是所有严格更小的情形，不包括正在证明的 $P(n)$。因此它没有把结论偷偷塞进前提，也不是循环论证。

强归纳证明的写法

下面的交互图可以在普通归纳和强归纳之间切换。拖动目标 $n$ 时，留意两种模式究竟开放了哪些可调用前提。

第一个完整例子：质因数分解的存在性

我们来证明：每个整数 $n\ge2$ 都能写成一个或多个素数的乘积。这里证明的是分解存在，不讨论分解是否唯一。

动笔前先暴露一下思路。目标是“素数乘积”，所以先问 $n$ 本身是不是素数。如果不是，合数的定义会把它拆成两个真因子。真因子严格小于原数，这就给强归纳假设留出了入口。

令 $P(n)$ 表示“整数 $n$ 可以写成一个或多个素数的乘积”。

为什么普通归纳的直接写法别扭，现在看得很清楚了。合数 $n$ 的两个因子可能离 $n-1$ 很远；证明需要 $P(a)$ 和 $P(b)$，强归纳假设恰好同时提供它们。

多个基础情形从哪里来

强归纳题里常见连续多个基础情形。它们不是为了让证明显得完整，而是在填补归纳步骤无法覆盖的起始空档。

考虑命题：每个不小于 $12$ 的整数，都可以写成若干个 $4$ 与若干个 $5$ 的和。令

我们的构造动作是“先组成 $n-4$，再加一个 $4$”。这条动作只有在 $n-4\ge12$ 时才能调用归纳假设，也就是从 $n\ge16$ 才开始运转。因此 $12,13,14,15$ 必须先逐个封住。

这个例子给出一个实用检查法：如果归纳步骤要回看前 $d$ 个位置，通常要检查最前面的 $d$ 个连续情形。这里每次减 $4$，所以先处理四个连续起点。只验证 $12$ 的话，$13$、$14$、$15$ 仍然无从得到。

良序原理：为什么可以抓住最小反例

良序原理说得很短：自然数的每个非空子集都有最小元素。用符号写就是，只要 $S\subseteq\mathbb{N}$ 且 $S\ne\varnothing$，就存在 $m\in S$，使得

定义里有两个条件都不能少。空集没有元素，自然谈不上最小元素；对象还必须来自自然数或其他良序集合。正有理数集合虽然非空，却没有最小正数，因为给出任何 $q>0$，总能再找到更小的正数 $q/2$。

还要分清“最小元素”和“下确界”。最小元素必须属于集合本身。良序原理保证的是集合里真有一个最靠前的成员，不只是存在某个集合外的下界。

自然数并不是唯一能这样使用的集合。任何有整数下界的整数集合也都有最小元素：把所有元素减去一个整数下界，就能把问题平移到自然数中。这也解释了为什么证明可以从任意整数起点 $n_0$ 开始，不必永远从 $0$ 开始。

最小反例法的骨架

假设我们想证明每个 $n\in\mathbb{N}$ 都满足 $P(n)$。若结论不成立，就把所有失败的下标收集起来：

如果真有反例，$C$ 就是非空自然数集合，因此有最小元素 $m$。接下来的任务并不是机械地重复定义，而是利用题目结构让这个最小反例崩掉。常见的崩法有两种：直接证明 $P(m)$ 其实成立，或者构造出另一个 $m'<m$ 且 $m'\in C$。

下面的交互页把这条推理放进质因数、邮资和算法终止三个场景。切换场景时，重点看每次选用的“规模”是什么，以及更小对象怎样被迫成为反例。

把质因数证明改写成最小反例

同一个质因数分解命题可以完全不用“归纳步骤”的格式。

假设有整数 $n\ge2$ 不能写成素数乘积，把它们组成集合 $C$。由良序原理，$C$ 有最小元素 $m$。$m$ 不会是素数，否则它自己就是一个素数乘积，所以 $m=ab$，其中 $$。由于 是最小反例，、 都不在 ，它们都能写成素数乘积。把这两个乘积相乘便得到 的素数分解，与 矛盾。因此 为空。

你会发现，这段证明与前面的强归纳证明几乎共享同一个核心：把合数拆成更小因子。差别只在叙述方向。强归纳说“所有更小情形已成立，所以当前情形成立”；最小反例法说“若当前是最小失败者，更小情形都成功，于是当前也成功，矛盾”。

普通归纳、强归纳与良序原理的关系

这三种方法在自然数上证明能力相同，但它们给读者看的思考路径不同。

普通归纳强调相邻传递。若基础情形成立，且每个 $P(n)$ 都能推出 $P(n+1)$，就不存在第一个失败位置：第一个失败位置的前一项本应成功，并把成功传给它。

强归纳强调全部前史。为了证明 $P(n)$，可以使用所有 $P(k)$，其中 $k<n$。如果想把它机械地改成普通归纳，只需定义一个更大的命题

普通归纳证明 $Q(n)\Rightarrow Q(n+1)$ 时，假设 $Q(n)$ 就等于一次拿到了从 $P(n_0)$ 到 的全部信息。这说明强归纳的“更强假设”可以被包装进一个普通归纳命题里。

良序原理强调第一个失败者。若基础情形与推进规则都成立，却仍有反例，那么反例集合有最小元素 $m$。最小性保证所有更小情形成功，推进规则又会迫使 $m$ 成功，于是矛盾。

递归定义不是一句自我指代

递归定义的表面特征，是定义里再次出现了被定义的对象。可只出现“自己”还不够。一个完整的递归定义必须告诉我们从哪里开始，以及怎样从已经得到的简单对象生成新对象。

对递归定义的集合或数据类型，最好把三件事说全：

1. 基础情形：哪些最简单的对象直接属于这个集合。
2. 构造规则：已知哪些旧对象后，可以怎样造出新对象。
3. 封闭说明：集合中只有通过有限次使用上述规则得到的对象，不额外混入其他对象。

第三条有时被写成“这是满足前两条的最小集合”。它防止定义只说明“哪些对象肯定在里面”，却没有排除无关对象。

从数列开始看生成过程

设数列由下面两条规则定义：

第一条给出起点，第二条把已经定义的 $a_n$ 送到下一项。于是

下面的展开器同时展示数列、字符串和二叉树。数列沿下标生长，字符串通过追加字符生长，二叉树则把一个问题分到左右子树。它们外形不同，却都遵守“基础对象加构造规则”的同一套语法。

自然数本身也能递归生成

自然数可以看成一个递归定义的数据类型：

• 基础情形：$0\in\mathbb{N}$。
• 构造规则：若 $n\in\mathbb{N}$，则它的后继 $n+1\in\mathbb{N}$。
• 封闭说明：自然数只有通过从 $0$ 出发、有限次取后继得到的对象。

现在回头看普通归纳，它其实就是沿着这份构造说明做结构归纳：先证明基础对象 $0$ 有性质，再证明构造器“取后继”会保持性质。

在递归对象上定义函数

对象怎样构造，作用在它上面的递归函数通常就怎样分情况。先规定函数在基础对象上的值，再用较小组成部分的函数值，定义新对象上的函数值。

阶乘沿自然数的后继结构定义：

斐波那契数每次要回看两个位置，所以需要两个基础值：

这里的两个基础值不是惯例装饰。若只给 $F_0$，计算 $F_2$ 时仍然缺少 $F_1$；递归规则不能唯一确定整条序列。

再看字符串。给定字母表 $A$，用 $A^*$ 表示所有有限字符串：

• 空字符串 $\varepsilon\in A^*$；
• 若 $a\in A$ 且 $s\in A^*$，则把 $a$ 接到 左端得到的 ；

字符串长度可以沿同样的结构递归定义：

注意右边调用的是更短字符串 $s$ 的长度。递归之所以能启动并得到唯一结果，是因为每次都沿构造历史向基础对象靠近。

怎样识别坏掉的递归定义

下面几类问题要格外小心。

1. 没有基础情形。 只写 $f(n)=2+f(n-1)$ 而不规定最初值，会留下无数种可能；任选 $f(0)$，都会生成一条不同的序列。
2. 没有向已定义对象靠近。 若规定 $f(0)=0$，而对 写 ，计算 会不断请求 ，永远碰不到基础情形；从方程角度看，正整数部分也没有被唯一确定。

结构归纳：证明要沿构造规则进入

递归定义告诉我们对象怎样造出来，结构归纳则照着同一张施工图证明性质。若递归类型 $R$ 有若干基础对象和若干构造器，要证明每个 $r\in R$ 都满足 $P(r)$，需要完成两类工作：

1. 对每个基础对象 $b$，直接证明 $P(b)$。
2. 对每个构造器，假设它的每个递归组成部分都满足 $P$，再证明构造出的新对象也满足 $P$。

一个二元构造器 $C(r,s)$ 对应的归纳步骤就是

这里为什么会同时出现两个归纳假设？因为新对象是由两个较小对象造出来的。结构归纳假设的数量，跟着构造器的递归参数数量走。

例子：字符串连接后的长度

先递归定义连接。固定任意字符串 $t$，按第一个字符串的结构规定：

我们要证明，对任意 $s,t\in A^*$，都有

证明入口应该选哪个对象？连接的递归定义是沿第一个参数 $s$ 展开的，所以对 $s$ 做结构归纳最自然。归纳命题要把另一个参数一并带上：

这份证明没有按字符串长度 $0,1,2,\ldots$ 明写下标，但每次都从 $ar$ 回到更短的 $r$。如果愿意，也能改成对长度做强归纳；结构归纳的优势是证明版式直接贴着对象的定义，不必另外发明一个数值下标。

二叉树里的两个归纳假设

设满二叉树递归定义如下：单个叶子是满二叉树；若 $L$、$R$ 是满二叉树，则用一个新根连接 $L$ 和 $R$ 得到的新树也是满二叉树。

令 $\ell(T)$ 表示叶子数，$i(T)$ 表示内部节点数。可以用结构归纳证明

基础情形是一片叶子，此时 $\ell=1$、$i=0$。构造情形假设 $\ell(L)=i(L)+1$ 且 $\ell(R)=i(R)+1$。新树满足

以及

因此

这里若只对左子树使用归纳假设，证明就会断掉。结构归纳必须覆盖构造器中的每个递归组成部分。

递归过程为什么会停下来

递归定义在数学上说明一个对象或函数怎样确定；递归程序还多了一个运行问题：照规则计算时，会不会真的到达基础情形？

常用办法是给每个状态 $x$ 指定一个自然数度量 $V(x)$，并证明每次非基础递归调用 $x\to x'$ 都满足

为什么“自然数值且严格下降”足以保证终止？假设存在无限调用链

那么度量值组成严格下降链

把这些度量值组成集合 $S$。由良序原理，$S$ 有最小元素 $V(x_j)$；可下一次调用又给出更小的 $V(x_{j+1})\in S$，矛盾。因此这样的无限调用链不存在。

欧几里得算法的度量

对整数 $a\ge b>0$，欧几里得算法使用

把第二个分量 $b$ 当作度量。除法余数满足

所以每次非基础调用都严格减小第二个分量。它最终只能到达第二个分量为 $0$ 的基础情形，算法因此终止。

常见错误集中检查

把强归纳假设写成了当前结论

错误写法是“假设 $P(k)$ 对所有 $k\le n$ 成立，证明 $P(n)$”。这个假设已经包含目标。正确边界应是 $k<n$；或者把目标写成 $P(n+1)$，假设范围写成 。

基础情形没有覆盖回看距离

若递推或构造每次要用 $n-2$，通常要先处理两个连续起点。若每次回看 $n-4$，就要检查四个余数类别对应的起点。强归纳不会自动填上开头的空档。

最小反例不在良序集合里

“取最小反例”需要先说明反例集合非空，并确认规模来自自然数或另一个良序集合。对正实数、正有理数直接取最小元素通常没有依据。

递归定义只写了生成规则

没有基础对象，生成过程无处开始；没有封闭说明，集合里可能混入没有被规则生成的对象；函数规则若不向更小组成部分靠近，还可能无法唯一确定值。

结构归纳漏掉构造器

递归定义若有两个基础对象、三个构造器，证明就必须逐项覆盖。只证明“最常见”的构造方式，不能推出所有递归生成对象都满足性质。

练习

选择证明方法

判断下面各题更适合普通归纳、强归纳、最小反例法还是结构归纳，并说明选择依据。

1. 证明 $1+2+\cdots+n=\frac{n(n+1)}{2}$。
2. 证明每个整数 $n\ge2$ 都是素数或素数乘积。

补全强归纳证明

证明每个整数 $n\ge8$ 都可以写成若干个 $3$ 与若干个 $5$ 的和。

找出递归定义的问题

有人想定义函数 $g:\mathbb{N}\to\mathbb{N}$：

这份定义为什么不能直接当作递归计算规则？

结构归纳练习

满二叉树由“单个叶子”和“把两棵满二叉树接到一个新根下”递归生成。证明每棵满二叉树的节点总数都是奇数。

从递归定义走向递推关系

现在可以把本章的三条线收拢起来了。普通归纳沿自然数的后继一步步走；强归纳在证明当前情形时允许查看全部更小情形；良序原理保证一旦真有失败者，就能抓住最小的那个。递归定义则把对象的生成历史写出来，结构归纳沿这段生成历史反向证明性质。

下一章会把注意力集中到数列。像

或

这样的式子叫递推关系。到那里，我们不只要确认递归定义完整，还会研究怎样展开递推式、猜出封闭公式，再用这一章学过的归纳方法验证猜想。换句话说，本章解决“规则能不能从简单对象生成全部对象”，下一章继续解决“生成出来的数列究竟长什么样”。

进一步说，因为值域被限定为 $\mathbb{N}$，反复使用等式还会迫使同一奇偶类上的函数值不断减去 $1$，最后变成负数。所以这不只是一个低效算法，而是根本没有定义出满足条件的全函数。