数学归纳法 vs 强归纳法

概述

数学归纳法（Mathematical Induction）和强归纳法（Strong Induction）都是证明对所有正整数成立的命题的核心技术。二者的基础步相同，核心区别在于归纳步的假设强度：普通归纳法仅假设 $P(k)$ 为真，强归纳法假设 $P(1)\wedge P(2)\wedge \cdots \wedge P(k)$ 全部为真。二者在逻辑上等价，但强归纳法在许多问题中更自然、更直接。

定义

数学归纳法

• 基础步：证明 $P(1)$ 为真
• 归纳步：证明 $\forall k\ge 1,P(k)\to P(k+1)$

形式化：$P(1)\wedge \forall k\ge 1[P(k)\to P(k+1)]⟹\forall n\ge 1,P(n)$

直觉类比：多米诺骨牌——第 1 块倒下，且每块倒下时必定推倒下一块。

强归纳法

• 基础步：证明 $P(1)$ 为真
• 归纳步：证明 $\forall k\ge 1,[P(1)\wedge P(2)\wedge \cdots \wedge P(k)]\to P(k+1)$

形式化：$P(1)\wedge \forall k\ge 1[(P(1)\wedge \cdots \wedge P(k))\to P(k+1)]⟹\forall n\ge 1,P(n)$

直觉类比：攀爬阶梯——每一步可以踩在之前所有台阶上。

对比维度

维度	数学归纳法	强归纳法
归纳假设	仅 $P(k)$	$P(1)\wedge P(2)\wedge \cdots \wedge P(k)$
假设强度	较弱	较强
逻辑力量	与强归纳法等价	与普通归纳法等价
直觉类比	踩在前一级台阶上	踩在之前所有台阶上
适用场景	结论仅依赖前一个情形	结论依赖多个前例
基础步	通常只需 $P(1)$	有时需要 $P(1)$ 和 $P(2)$
别名	第一数学归纳法	完全归纳法、第二数学归纳法
典型应用	求和公式、不等式、整除性	算术基本定理唯一性、博弈策略、三角剖分

关键区别

• 普通归纳法的归纳步只”看一步”，强归纳法的归纳步”看所有之前的步骤”
• 强归纳法并不比普通归纳法”更强”——二者可以互相推出，是等价的证明方法
• 强归纳法通过构造辅助命题 $Q(n)$ = "$\forall j\le n,P(j)$" 可以转化为普通归纳法
• 在实际使用中，强归纳法往往更方便，避免了构造辅助命题的麻烦
• 强归纳法的基础步有时需要验证多个初始值（如 $P(1)$ 和 $P(2)$），因为归纳步可能引用 $P(k-1)$

联系

• 二者都与良序性等价——良序性、普通归纳法、强归纳法三者互相等价
• 二者都是证明递归定义和递归算法正确性的核心工具
• 强归纳法是结构归纳的基础——将”所有更小整数”推广为”所有更小子结构”
• 选择哪种归纳法取决于问题的结构：如果 $P(k+1)$ 只依赖 $P(k)$，用普通归纳法；如果依赖多个前例，用强归纳法
• 在第5章中，5.1 节介绍普通归纳法，5.2 节介绍强归纳法，二者共同构成归纳证明的完整体系

参见

• 数学归纳法 — 数学归纳法的完整概念卡片