普通归纳法只由 推出 。很多自然的命题并不是这样运作:合数可以分解为两个较小的数,但它们不一定是 ;递归定义的序列可能依赖前面两项或更多项。本单元由良序原理证明强归纳法,并说明它的用法,以及与之等价的最小反例方法。内容建立在单元 1.2 对证明结构与普通归纳法的讨论之上。
良序原理
定义 1.4.1
(良序原理)
令 。良序原理指出: 的每个非空子集 都有最小元素,即存在 ,对所有 有 。经平移后,同一结论对每个有下界的非空整数集合也成立。
这个原理对 失效( 本身没有最小元素),对正实数也失效(集合 没有最小元素)。
反例模式
离开自然数,良序性便失效
命题:每个非空的正有理数集合都有最小元素。取 。它非空,而对任何成员 ,成员 严格较小,因为 给出 。所以 没有最小成员。命题对 不成立;补救是保留“集合由有下界的整数组成”这个假设,那正是原理所要求的。
强归纳法
定理 1.4.2
(强归纳法)
设 为整数,对每个整数 给定命题 。假设对每个整数 ,下列蕴含成立:
则 对每个整数 都成立。
证明
(取最小的失败者)
假设不然。集合 非空且有下界,所以有最小元素 。由 的最小性,对每个满足 的 , 成立。于是定理的假设给出 ,与 矛盾。
证明透视
为何不需要单独的基础情形
证明只用了一次良序原理,即在失败集中取最小元素;也只用了一次归纳假设,即在那个最小元素处。最小性一次提供了整个前提:每个较小的指标都不在 中,所以 对它们全部成立。这就是强归纳法不需要明确基础情形的原因。对 ,前提“对所有 有 ”不涉及任何指标,是空泛地成立,所以 处的蕴含直接断言 。证明没有说明怎样证明这个蕴含,实际工作和实际的基础情形正是出现在那里。有下界是必要的:否则 未必有最小元素,论证便无从选取。
两点说明。第一,实际操作时会先单独证明最初的几个情形,因为一般步骤通常至少要引用一个更早的情形。第二,普通归纳法是步骤只用 的特例。
因此强归纳法的证明形式如下:固定 ,假设对所有更早的 有 ,再证明 。当论证引用具体的更早情形,如 或 时,必须检查这些指标不小于 ,这就是需要几个基础情形的原因。
最小反例方法
强归纳法的证明可以直接使用。要证明 ,假设反例集合非空,取其最小元素 ,并由每个较小指标都满足 这一事实导出矛盾。这在逻辑上与强归纳法相同;选择读起来较清楚的一种即可。
例题
例题 1.4.3
(素因数分解存在)
每个整数 都是一个或多个素数的乘积。 用 的强归纳法。设 ,并假设结论对所有满足 的 成立。若 是素数,它就是一个素数的乘积。否则 ,其中 。由假设, 与 都是素数的乘积,所以 也是。
注意论证对两个不同的更早数值 和 使用了假设,而它们都不是预先确定为 。
例题 1.4.4
(面值为四和五的邮票)
每个整数 都可写成 ,其中 为整数。 步骤引用 ,只有当 时 才不小于 ,所以要证明四个基础情形:,,,。现设 ,并假设结论对所有满足 的 成立。由于 且 ,有 ,,所以 。
例题 1.4.5
(二进制表示存在)
每个整数 都是若干个互不相同的 的幂之和。 取 ,并假设结论对所有 成立。若 ,则 。若 ,令 是不超过 的最大的 的幂,即 。若 ,已完成。否则 满足 ,因为 。由假设, 是互不相同的 的幂之和,其中每项至多为 ,所以没有一项等于 。加上 便得到 的所求表示。
例题 1.4.6
(递归序列)
定义 、,并对 令 。最初几项是 。断言:对所有 ,。 需要两个基础情形: 和 。设 ,并假设公式对 与 成立。利用 与 ,
边界情形是第一个指标 ,此时步骤同时回到两个基础情形。
常见错误与细节
常见错误
(基础情形太少)
若步骤引用 ,则 已经引用到 ,它在范围之外。 与 都必须单独证明。在邮票的例子中,步骤引用 ,因此需要四个基础情形。
常见错误
(在 n 处或范围外使用假设)
在归纳步骤中,只可对 使用 ,绝不能使用 本身。指标也必须落在容许的范围内:在分解的例子中,分解 必须满足 ,假设才能同时用于两个因数。
常见错误
(在非良序集合上用最小反例)
最小反例的论证适用于 或有下界的整数集合的子集,不适用于 的子集:像 这样的反例集合没有最小元素。若步骤只需要 ,普通归纳法更清楚。
练习
快速检查
(由序列例题中的递推式,证明对每个 , 都是整数。)
用强归纳法证明递推式产生的都是整数。
解答 · 引导解答
由递推式 、、 定义 。对 用强归纳法证明 :基础情形 与 都是整数;对 ,整数 给出整数 。由于闭式等于 (见序列例题),所以对每个 , 都是整数。(例如 给出 。)
快速检查
(证明每个整数 都可写成 ,其中 为整数。)
步骤回溯 格,先决定需要多少个基础情形。
解答 · 引导解答
基础情形:,,。设 ,并假设结论对所有满足 的 成立。由于 且 ,有 ,,所以 。因为步骤回溯 格,所以需要三个基础情形。
快速检查
(设 ,且对 有 。证明对所有 有 。)
两个基础情形,再用前两个界估计 。
解答 · 引导解答
基础情形: 与 。设 ,并假设对所有 有 。则
快速检查
(利用良序原理证明不存在整数 使 。)
假设这种整数的集合非空,考虑它的最小元素 。
解答 · 引导解答
假设满足 的整数 所成的集合 非空。则 ,有最小元素 。由于 ,把不等式 乘以正数 得 ,且 。又 。所以 是整数且 ,即 ,而 与 的最小性矛盾。因此 为空集。