强归纳法是一种数学证明方法,用于证明某个命题对每个自然数,或对不小于某个指定起始值的每个整数都成立。在归纳步骤中,可以假设该命题对相关范围内的所有较小值均成立,而不仅仅是对紧邻的前一个值成立。尽管名称中有“强”字,在标准的自然数算术框架下,强归纳法与普通的数学归纳法在逻辑上是等价的。它的优势在于,归纳假设往往能更直接地契合问题的结构。
原理与形式化表述
设 是关于整数 的命题, 是所考虑的起始值。标准的强归纳法证明需要确立以下两点:
- 基础情形: 成立。
- 归纳步骤: 对每个 ,如果 对满足 的每个整数 都成立,那么 成立。
由此得出结论: 对每个整数 都成立。
用符号表示,前提为
以及
假设
称为强归纳假设。它允许使用此前的每一种情形,不过具体证明中可能只会用到其中的一两个。
另一种等价表述将基础情形纳入一个统一条件:
当 时,指定的 的取值范围内没有整数。因此,关于此前各情形的假设空真,所以该条件要求在不借助任何此前假设的情况下, 成立。
方法的使用步骤
强归纳法证明通常遵循以下步骤:
- 明确命题 及其起始值。
- 证明一个或多个基础情形。
- 任取一个后续值 。
- 假设 对所有相关的 成立。
- 推导出 ,并检查每次使用归纳假设时,所用下标都严格小于当前下标,且位于规定范围内。
如果归纳步骤需要回溯不止一个位置,就可能需要多个基础情形。例如,若定理的起始值为 ,归纳步骤由 推出 ,那么通常需要分别证明 、 和 这三个基础情形。
归纳假设是临时的、有条件的。证明并不是假定所要证明的定理已经对所有数成立,而是证明:只要此前所有情形都成立,就能推出当前情形也成立。随后,归纳原理便可保证全称结论成立。
与普通归纳法的等价性
普通归纳法通常使用如下步骤:
强归纳法则允许在证明 时使用更广泛的假设:
这在归纳步骤内部提供了更多信息,但并不意味着整个证明原理更强。
为了从普通归纳法推导出强归纳法,定义累积命题:
基础情形 恰好就是 。如果 成立,那么从 到 的每一种情形都可供使用。因此,由强归纳步骤可得 ,再结合此前各情形,便可确立 。普通归纳法证明了 对每个 都成立,从而证明了每个 。
反过来,普通归纳法也可由强归纳法推出,因为强归纳假设包含紧邻的前一个情形。如果仅这一种情形就已足够,其余假设不使用即可。
因此,两种方法的选择,主要取决于哪一种归纳假设更符合命题中各情形之间的依赖关系。
示例
素因数分解的存在性
数论中的一个标准例子是以下命题:
每个整数 都可以表示为有限个素数的乘积。
用 表示这一命题。
基础情形。 数 是素数,因此它本身就是仅含一个素因子的乘积。
归纳步骤。 设 ,并假设满足 的每个整数 都是若干素数的乘积。
如果 是素数,命题立即成立。否则, 可以分解为
由归纳假设, 和 都是若干素数的乘积。将这两个乘积相乘,就将 表示成了若干素数的乘积。
因此,强归纳法证明了该命题对所有 都成立。
这证明了算术基本定理中的存在性部分,并未证明唯一性;唯一性需要另行论证。这里使用强归纳法很自然,因为所涉及的较小数是 的因子,而不一定是 。
斐波那契数列的一个上界
设斐波那契数列定义为
用强归纳法可证明
基础情形为
对于 ,假设该上界对每个较小的非负下标都成立。于是
这里只用到了此前的两种情形,而强归纳假设允许同时使用它们。这在涉及递推关系的证明中很常见。也可以将两个相邻的上界合并为一个命题,再用普通归纳法组织同一个证明。
用两种面额表示整数
每个整数 都可以写成
其中 和 为非负整数。
四个基础情形为:
对于 ,假设从 到 的每个整数都有这样的表示。由于
由归纳假设可得 。因此,
这里的归纳步骤向前回溯四个位置,而这四个基础情形提供了所需的起点。
良序性与最小反例
强归纳法与良序原理密切相关:自然数的每个非空子集都有最小元素。
经典的反证法可以解释二者之间的联系。假设基础情形和强归纳步骤都成立,但某个 为假。那么,反例集合中存在最小元素 。基础情形排除了 的可能性,而 的最小性意味着,对每个相关的 , 都为真。因此,由归纳步骤可得 成立,这与它被选为反例相矛盾。
这种方法通常称为最小反例论证。在标准的经典算术论述中,在适当的背景假设下,普通归纳法、强归纳法和良序原理是彼此等价的表述。利用累积命题直接证明两种归纳法等价时,并不需要最小反例论证。
应用与推广
当一个大小为 的对象被归约为若干大小不一的较小对象时,强归纳法尤其有用。例如,因数分解论证、递归定义的数列,以及递归算法的正确性证明。
在算法应用中,可以将输入规模作为归纳参数:利用算法对所有较小输入的正确性,证明其对当前输入的正确性。这样的论证还必须说明,每次递归调用都会使所选的度量减小,并且所有基础情形都得到了处理。
更一般的原理是良基归纳法。给定一个良基关系 ,可以通过假设每个前驱 都满足 ,来证明 。强归纳法是采用自然数上通常的严格序关系的特例。
结构归纳法根据递归生成对象的构造方式来组织证明,例如表达式或有限树的构造。它与强归纳法密切相关,不过它的归纳假设涉及组成部分的结构,而不一定涉及数值下标更小的所有对象。
常见错误与适用范围
以下几种错误可能使强归纳法论证失效:
- 遗漏基础情形。 使用 的归纳步骤,只有在 落入已确立的范围后才能应用。
- 循环使用结论。 归纳假设只涵盖严格较小的下标;证明 时,不能假设 成立。
- 使用定理定义域之外的下标。 如果下标小于 ,那么仅仅小于 并不足以使用归纳假设。
- 未覆盖所有取值。 若归纳步骤每次前进一个固定的数值,就需要足够多的基础情形,才能到达所有预期取值。
强归纳法可直接用于自然数,以及具有最小起始值的整数范围。它不能原封不动地用于通常次序下的全体整数,也不能用于通常严格次序下的实数,因为这些序关系并非良基关系。要推广到其他论域,需要适当的良基关系或其他归纳原理。