aiwiki.page
中文
数学 / 离散数学与逻辑 / strong-induction

强归纳法

强归纳法通过假设所有较小情形均成立来证明当前情形,从而证明命题对每个自然数都成立。

14 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
数学证明自然数数学归纳法整数数论素数算术基本定理斐波那契数列强归纳法

强归纳法是一种数学证明方法,用于证明某个命题对每个自然数,或对不小于某个指定起始值的每个整数都成立。在归纳步骤中,可以假设该命题对相关范围内的所有较小值均成立,而不仅仅是对紧邻的前一个值成立。尽管名称中有“强”字,在标准的自然数算术框架下,强归纳法与普通的数学归纳法在逻辑上是等价的。它的优势在于,归纳假设往往能更直接地契合问题的结构。

原理与形式化表述

设 P(n)P(n) 是关于整数 nn 的命题,n0n_0 是所考虑的起始值。标准的强归纳法证明需要确立以下两点:

  1. 基础情形: P(n0)P(n_0) 成立。
  2. 归纳步骤: 对每个 n>n0n>n_0,如果 P(k)P(k) 对满足 n0≤k<nn_0\leq k<n 的每个整数 kk 都成立,那么 P(n)P(n) 成立。

由此得出结论:P(n)P(n) 对每个整数 n≥n0n\geq n_0 都成立。

用符号表示,前提为

P(n0)P(n_0)

以及

∀n>n0,[(∀k, n0≤k<n⇒P(k))⇒P(n)].\forall n>n_0,\qquad \left[ \left(\forall k,\ n_0\leq k<n\Rightarrow P(k)\right) \Rightarrow P(n) \right].

假设

∀k,n0≤k<n⇒P(k)\forall k,\qquad n_0\leq k<n\Rightarrow P(k)

称为强归纳假设。它允许使用此前的每一种情形,不过具体证明中可能只会用到其中的一两个。

另一种等价表述将基础情形纳入一个统一条件:

[∀n≥n0,(∀k, n0≤k<n⇒P(k))⇒P(n)]⇒∀n≥n0, P(n).\left[ \forall n\geq n_0,\quad \left(\forall k,\ n_0\leq k<n\Rightarrow P(k)\right) \Rightarrow P(n) \right] \Rightarrow \forall n\geq n_0,\ P(n).

当 n=n0n=n_0 时,指定的 kk 的取值范围内没有整数。因此,关于此前各情形的假设空真,所以该条件要求在不借助任何此前假设的情况下,P(n0)P(n_0) 成立。

方法的使用步骤

强归纳法证明通常遵循以下步骤:

  • 明确命题 P(n)P(n) 及其起始值。
  • 证明一个或多个基础情形。
  • 任取一个后续值 nn。
  • 假设 P(k)P(k) 对所有相关的 k<nk<n 成立。
  • 推导出 P(n)P(n),并检查每次使用归纳假设时,所用下标都严格小于当前下标,且位于规定范围内。

如果归纳步骤需要回溯不止一个位置,就可能需要多个基础情形。例如,若定理的起始值为 n0n_0,归纳步骤由 P(n−3)P(n-3) 推出 P(n)P(n),那么通常需要分别证明 n0n_0、n0+1n_0+1 和 n0+2n_0+2 这三个基础情形。

归纳假设是临时的、有条件的。证明并不是假定所要证明的定理已经对所有数成立,而是证明:只要此前所有情形都成立,就能推出当前情形也成立。随后,归纳原理便可保证全称结论成立。

与普通归纳法的等价性

普通归纳法通常使用如下步骤:

P(n)⇒P(n+1).P(n)\Rightarrow P(n+1).

强归纳法则允许在证明 P(n+1)P(n+1) 时使用更广泛的假设:

P(n0),P(n0+1),…,P(n)P(n_0),P(n_0+1),\ldots,P(n)

这在归纳步骤内部提供了更多信息,但并不意味着整个证明原理更强。

为了从普通归纳法推导出强归纳法,定义累积命题:

Q(n):∀k, n0≤k≤n⇒P(k).Q(n):\quad \forall k,\ n_0\leq k\leq n\Rightarrow P(k).

基础情形 Q(n0)Q(n_0) 恰好就是 P(n0)P(n_0)。如果 Q(n)Q(n) 成立,那么从 n0n_0 到 nn 的每一种情形都可供使用。因此,由强归纳步骤可得 P(n+1)P(n+1),再结合此前各情形,便可确立 Q(n+1)Q(n+1)。普通归纳法证明了 Q(n)Q(n) 对每个 n≥n0n\geq n_0 都成立,从而证明了每个 P(n)P(n)。

反过来,普通归纳法也可由强归纳法推出,因为强归纳假设包含紧邻的前一个情形。如果仅这一种情形就已足够,其余假设不使用即可。

因此,两种方法的选择,主要取决于哪一种归纳假设更符合命题中各情形之间的依赖关系。

示例

素因数分解的存在性

数论中的一个标准例子是以下命题:

每个整数 n≥2n\geq 2 都可以表示为有限个素数的乘积。

用 P(n)P(n) 表示这一命题。

基础情形。 数 22 是素数,因此它本身就是仅含一个素因子的乘积。

归纳步骤。 设 n>2n>2,并假设满足 2≤k<n2\leq k<n 的每个整数 kk 都是若干素数的乘积。

如果 nn 是素数,命题立即成立。否则,nn 可以分解为

n=ab,2≤a<n,2≤b<n.n=ab,\qquad 2\leq a<n,\qquad 2\leq b<n.

由归纳假设,aa 和 bb 都是若干素数的乘积。将这两个乘积相乘,就将 nn 表示成了若干素数的乘积。

因此,强归纳法证明了该命题对所有 n≥2n\geq 2 都成立。

这证明了算术基本定理中的存在性部分,并未证明唯一性;唯一性需要另行论证。这里使用强归纳法很自然,因为所涉及的较小数是 nn 的因子,而不一定是 n−1n-1。

斐波那契数列的一个上界

设斐波那契数列定义为

F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2).F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\geq 2).

用强归纳法可证明

Fn≤2n(n≥0).F_n\leq 2^n\qquad(n\geq 0).

基础情形为

F0=0≤1,F1=1≤2.F_0=0\leq 1,\qquad F_1=1\leq 2.

对于 n≥2n\geq 2,假设该上界对每个较小的非负下标都成立。于是

Fn=Fn−1+Fn−2≤2n−1+2n−2=3⋅2n−2≤2n.F_n =F_{n-1}+F_{n-2} \leq 2^{n-1}+2^{n-2} =3\cdot 2^{n-2} \leq 2^n.

这里只用到了此前的两种情形,而强归纳假设允许同时使用它们。这在涉及递推关系的证明中很常见。也可以将两个相邻的上界合并为一个命题,再用普通归纳法组织同一个证明。

用两种面额表示整数

每个整数 n≥12n\geq 12 都可以写成

n=4a+5bn=4a+5b

其中 aa 和 bb 为非负整数。

四个基础情形为:

12=4+4+4,13=4+4+5,12=4+4+4,\qquad 13=4+4+5,
14=4+5+5,15=5+5+5.14=4+5+5,\qquad 15=5+5+5.

对于 n≥16n\geq 16,假设从 1212 到 n−1n-1 的每个整数都有这样的表示。由于

12≤n−4<n,12\leq n-4<n,

由归纳假设可得 n−4=4a+5bn-4=4a+5b。因此,

n=4(a+1)+5b.n=4(a+1)+5b.

这里的归纳步骤向前回溯四个位置,而这四个基础情形提供了所需的起点。

良序性与最小反例

强归纳法与良序原理密切相关:自然数的每个非空子集都有最小元素。

经典的反证法可以解释二者之间的联系。假设基础情形和强归纳步骤都成立,但某个 P(n)P(n) 为假。那么,反例集合中存在最小元素 mm。基础情形排除了 m=n0m=n_0 的可能性,而 mm 的最小性意味着,对每个相关的 k<mk<m,P(k)P(k) 都为真。因此,由归纳步骤可得 P(m)P(m) 成立,这与它被选为反例相矛盾。

这种方法通常称为最小反例论证。在标准的经典算术论述中,在适当的背景假设下,普通归纳法、强归纳法和良序原理是彼此等价的表述。利用累积命题直接证明两种归纳法等价时,并不需要最小反例论证。

应用与推广

当一个大小为 nn 的对象被归约为若干大小不一的较小对象时,强归纳法尤其有用。例如,因数分解论证、递归定义的数列,以及递归算法的正确性证明。

在算法应用中,可以将输入规模作为归纳参数:利用算法对所有较小输入的正确性,证明其对当前输入的正确性。这样的论证还必须说明,每次递归调用都会使所选的度量减小,并且所有基础情形都得到了处理。

更一般的原理是良基归纳法。给定一个良基关系 ≺\prec,可以通过假设每个前驱 y≺xy\prec x 都满足 P(y)P(y),来证明 P(x)P(x)。强归纳法是采用自然数上通常的严格序关系的特例。

结构归纳法根据递归生成对象的构造方式来组织证明,例如表达式或有限树的构造。它与强归纳法密切相关,不过它的归纳假设涉及组成部分的结构,而不一定涉及数值下标更小的所有对象。

常见错误与适用范围

以下几种错误可能使强归纳法论证失效:

  • 遗漏基础情形。 使用 P(n−r)P(n-r) 的归纳步骤,只有在 n−rn-r 落入已确立的范围后才能应用。
  • 循环使用结论。 归纳假设只涵盖严格较小的下标;证明 P(n)P(n) 时,不能假设 P(n)P(n) 成立。
  • 使用定理定义域之外的下标。 如果下标小于 n0n_0,那么仅仅小于 nn 并不足以使用归纳假设。
  • 未覆盖所有取值。 若归纳步骤每次前进一个固定的数值,就需要足够多的基础情形,才能到达所有预期取值。

强归纳法可直接用于自然数,以及具有最小起始值的整数范围。它不能原封不动地用于通常次序下的全体整数,也不能用于通常严格次序下的实数,因为这些序关系并非良基关系。要推广到其他论域,需要适当的良基关系或其他归纳原理。