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

上一章的普通归纳像沿着一排台阶向前走：证明第一阶能站住，再证明从第 $n$ 阶能走到第 $n+1$ 阶。很多离散问题却不是这样。证明当前结论时，我们可能需要同时使用多个更小情形，而不是只用紧邻的前一步。

本章处理这类问题。强归纳让归纳假设覆盖所有更小对象；良序原理把“若有反例，就有最小反例”变成可用的证明工具；递归定义则用基础情形和生成规则描述对象如何一步一步长出来。

本章默认自然数从 $0$ 开始，即 $\mathbb{N}=\{0,1,2,\dots\}$ 。如果题目从 $1$ 、 $2$ 或某个门槛 $n_0$ 开始，只需要把基础情形和归纳步骤的起点相应平移。

从普通归纳到强归纳

普通归纳证明一个命题族 $P(n)$ 时，典型结构是：

证明基础情形 $P(n_0)$ 。
假设 $P(n)$ 成立。
证明 $P(n+1)$ 成立。

强归纳把第 2 步改宽。为了证明 $P(n)$ ，它允许我们假设所有更小情形都已经成立：

P(n_0),P(n_0+1),\dots,P(n-1)

这并不是改变要证明的结论，而是改变归纳步骤中能调用的材料。

普通归纳与强归纳对比图，左侧表示只由 P(n) 推到 P(n+1)，右侧表示由 P(0)、P(1) 到 P(n) 等所有更小情形共同推出 P(n+1)。

普通归纳适合“下一步只依赖上一步”的问题。求和公式、简单整除式、不等式递推，往往属于这一类。强归纳适合“当前对象可能拆成多个更小对象”的问题。质因数分解、递归算法、树结构、邮资组合和很多计数递推，都经常需要它。

强归纳的标准模板

要证明对所有 $n\ge n_0$ ，命题 $P(n)$ 成立，可以这样写：

先证明所有必要的基础情形。基础情形不一定只有一个；如果归纳步骤会回看 $4$ 步，就可能需要连续证明几个起点。

在归纳步骤中取任意 $n>n_0$ 。假设对每个整数，只要，命题就成立。

强归纳证明依赖图：左侧 P(0)、P(1)、P(2) 到 P(n-1) 的命题节点通过箭头汇入当前目标 P(n)，下方标出自然数轴，右上角说明所有 k 小于 n 的 P(k) 已成立。

强归纳的常见错误是把归纳假设写得很宽，却在证明中没有真正使用它。写完归纳步骤后，应回头检查：当前 $P(n)$ 到底依赖了哪个更小的 $P(k)$ ？如果完全没有用到归纳假设，这个证明可能只是直接证明。

下面的交互图可以切换普通归纳和强归纳。选择目标 $n$ 后，观察证明 $P(n)$ 时哪些更小命题可以被调用。

良序原理

良序原理说：自然数的任意非空子集都有最小元素。也就是说，只要 $S\subseteq\mathbb{N}$ 且 $S$ 非空，就存在 $m\in S$ ，使得对所有 $s\in S$ ，都有 $m\le s$ 。

自然数轴上集合 S 的若干元素被圈出，最左边的元素 2 用红色标记和放大镜突出，说明非空自然数集合必有最小元素。

这个原理看起来很朴素，但它和归纳法关系很紧。强归纳常常可以改写成良序原理证明：如果结论不总成立，那么反例集合非空；良序原理给出最小反例；再用证明结构推出一个更小反例，于是矛盾。

在自然数上，普通归纳、强归纳和良序原理的证明能力是等价的。实际写证明时，它们的差别主要在表达方式：普通归纳强调一步一步推进，强归纳强调可调用所有更小情形，良序原理强调不存在最小反例。

最小反例法

最小反例法是良序原理的常用写法。它适合证明“所有自然数对象都满足某性质”的命题，尤其适合那些可以把失败对象拆成更小失败对象的问题。

一般步骤如下：

假设命题并非总成立。把所有反例放进集合 $C$ 。

由于假设存在反例， $C$ 是非空自然数集合。由良序原理， $C$ 有一个最小元素 $m$ 。

最小反例法示意图：左侧反例集合中圈出最小反例 m，中间构造更小反例，右侧出现 m' 小于 m 并标出矛盾。

下面的交互工具把最小反例法拆成三个场景：质因数分解、邮资拆分和算法终止。切换场景后，注意“更小对象”分别是什么。

质因数分解存在性

强归纳最经典的例子之一是证明：每个整数 $n\ge 2$ 都可以写成若干素数的乘积。这里只证明“存在性”，不讨论分解唯一性。

用强归纳证明质因数分解存在性的因子树图：84 分解为 6 乘 14，再分解为素数 2、3、2、7，并标注合数分解时更小因子调用归纳假设。

命题记为 $P(n)$ ：整数 $n$ 可以写成一个或多个素数的乘积。

基础情形是 $n=2$ 。因为 $2$ 本身是素数，所以 $2$ 已经是一个素数的乘积。

归纳假设：取任意 $n>2$ ，假设对所有整数，只要，命题都成立。

这个证明的关键不是“从 $n-1$ 到 $n$ ”。当 $n=84$ 时，它自然拆成 $6$ 和 $14$ ；证明 $84$ 的结论需要用到 $6$ 和的结论，而不是只用的结论。强归纳正好允许这样的调用。

不要把“合数可以分成两个更小因子”写成一句含糊的直觉。归纳假设能被调用，是因为这两个因子都落在区间 $2\le k\lt n$ 内。这个范围检查是强归纳证明中最容易漏掉的一步。

递归定义

递归定义用两类信息定义对象：

基础情形：直接给出最小对象或最初几项。
递归规则：说明如何由已经定义的较小对象生成新的对象。

例如，序列可以这样定义：

a_0=1

a_{n+1}=2a_n+1

这个定义不是先给出封闭公式，而是给出生成方法。先有 $a_0=1$ ，再算 $a_1=3$ ，接着 $a_2=7$ ，然后。

递归定义由基础情形和递归规则组成，示例从 a_0 = 1 和 a_n+1=2a_n+1 生成序列 1、3、7、15，并展示小型递归树。

递归定义和强归纳经常一起出现。递归定义负责说明对象如何由较小对象生成；强归纳负责证明每个生成出来的对象都满足某性质。

递归定义必须说明“从哪里开始”和“怎样继续”。只有递归规则而没有基础情形，会导致对象无处起步；只有基础情形而没有递归规则，则只能定义少数几个对象。

下面的展开器展示三类递归定义：数列、字符串和二叉树。切换类型时，留意基础情形和递归规则的位置。

用归纳验证递归定义的性质

设 $a_0=1$ ， $a_{n+1}=2a_n+1$ 。证明对所有，

a_n=2^{n+1}-1

基础情形：当 $n=0$ 时，左边 $a_0=1$ ，右边 $2^{1}-1=1$ ，所以命题成立。

这个例子只需要普通归纳，因为每一项只依赖前一项。若一个对象依赖多个更小对象，比如一棵树的左右子树，证明时通常更自然地使用强归纳或结构归纳。

算法终止

很多递归算法的正确性证明分成两部分：它会停下来，它停下后结果正确。本章先关注终止性。

证明终止的常见思路是找一个自然数度量 $V$ ，它衡量问题规模。每次递归调用都让 $V$ 严格变小。自然数不能无限严格下降，所以算法最终必须到达基础情形。

中文教学图，左侧展示递归调用从问题规模 n 逐步变小直到基础情形，右侧用下降台阶说明度量 V(n) 每步严格下降且不能无限下降。

以欧几里得算法为例。对正整数 $a\ge b$ ，算法用

\gcd(a,b)=\gcd(b, a\bmod b)

不断替换二元组，直到第二个数为 $0$ 。这里可以用第二个分量作为度量。只要 $b>0$ ，余数 $a\bmod b$ 满足

0\le a\bmod b<b

所以第二个分量严格下降。它是自然数，不可能无限下降，因此算法终止。

终止证明的核心句式是：度量取自然数值，并且每次非基础调用都会严格变小。良序原理保证不存在无限下降链。

邮资与多重基础情形

有些强归纳题需要多个基础情形。例子：证明每个不小于 $12$ 的邮资金额都可以用 $4$ 分邮票和 $5$ 分邮票组成。

命题 $P(n)$ ：金额 $n$ 可以写成 $4a+5b$ ，其中 $a,b$ 是非负整数。

先验证四个基础情形： $12=4+4+4$ ， $13=4+4+5$ ，，。

邮资拆分类例题信息图，展示 12、13、14、15 分邮资由 4 分和 5 分邮票组成，并说明若已能组成 n−4，则加一枚 4 分邮票组成 n。

这个证明说明了为什么基础情形有时必须是一段连续区间。归纳步骤要从 $n$ 回看 $n-4$ ，所以只有验证 $12,13,14,15$ ，才能保证从 $16$ 开始每一步都能落回已经覆盖的范围。

如果只验证 $12$ 这一个基础情形，归纳步骤无法证明 $13$ 、 $14$ 、 $15$ 。强归纳并不会自动补齐缺失的起点；基础情形必须覆盖递归或回看规则留下的空档。

选择哪一种证明写法

遇到自然数命题时，可以用下面的判断来选择写法。

问题特征	更自然的写法	典型例子
当前情形只依赖上一情形	普通归纳	求和公式、简单递推
当前情形可能依赖多个更小情形	强归纳	质因数分解、邮资金额、递归树
想证明不存在反例	良序原理或最小反例法	算法终止、极小对象矛盾
对象由规则生成	递归定义配合归纳证明	字符串、树、递归序列

写证明前先问一句：当前对象怎样变成更小对象？如果答案是“减一”，普通归纳通常够用；如果答案是“拆成几个较小部分”或“跳回某个较小值”，强归纳通常更顺手。

练习

判断证明方法

对每个命题，判断更适合普通归纳、强归纳还是最小反例法，并说明原因。

对所有 $n\ge 1$ ，有 $1+2+\cdots+n=\frac{n(n+1)}{2}$ 。

普通归纳更自然，因为从 $n$ 到 $n+1$ 只需要多加一项。
强归纳更自然，因为合数 $n$ 会拆成两个更小因子，不一定是 $n-1$ 。
最小反例法或强归纳都自然。终止性可以用自然数度量严格下降来说明，也可以说若有不终止的最小规模，就会调用更小的不终止规模，矛盾。
强归纳更自然，因为构造 $n$ 时可能要回看 $n-4$ 或，基础情形也可能不止一个。

补全强归纳证明

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

先验证 $8=3+5$ 、 $9=3+3+3$ 、 $10=5+5$ 。对，利用，再加一个。

设 $P(n)$ 表示 $n$ 可以写成若干个 $3$ 和 $5$ 的和。基础情形为 $8=3+5$ 、 $9=3+3+3$ 、。现在取任意，假设所有的都成立。因为且，所以由归纳假设，可以写成若干个和的和。再加一个，就得到的表示。因此由强归纳法，所有都可以写成若干个和的和。

递归定义与公式

设 $b_0=2$ ， $b_{n+1}=3b_n$ 。猜测的封闭公式，并用归纳法证明。

前几项是 $2,6,18,54,\dots$ ，所以猜测 $b_n=2\cdot 3^n$ 。基础情形 $n$ 时，右边是，与相同。假设，则由递归定义，。因此公式对所有成立。

最小反例练习

用最小反例法说明：如果一个递归过程的输入规模是自然数，并且每次递归调用都把规模严格变小，那么这个过程不可能无限递归。

假设存在会无限递归的输入规模。把所有这类规模放入集合 $C$ 。由良序原理， $C$ 有最小元素 $m$ 。规模为 $m$ 的过程如果不是基础情形，就会递归调用某个更小规模 $m'\lt m$ 。因为原过程会无限递归，某条后续调用链也必须从更小规模继续无限递归，所以 $m^{'} \in C$ 。这与是的最小元素矛盾。因此不存在无限递归的输入规模。

本章小结

强归纳适合处理“当前情形依赖多个更小情形”的命题。良序原理把这类证明改写成最小反例法：假设有失败对象，取最小失败对象，再推出更小失败对象，从而矛盾。递归定义则从另一侧说明对象如何由基础情形和递归规则生成。

学完本章后，看到一个自然数命题时，不要先急着套模板。先找它的“变小结构”：是从 $n$ 到 $n+1$ ，还是从 $n$ 回到若干个更小对象？这个判断通常决定了证明会写得顺不顺。

=

0

n=0

m'\in C

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 10 章：强归纳、良序原理与递归定义 | 自在学