1.3 归纳法与递归定义

1.3 归纳法与递归定义

本节摘要：数学归纳法用"归纳基础 + 归纳步骤"两步证明无穷多个命题，是处理自然数命题的标准武器；递归定义则是它的镜像——用自身定义自身。本节讲清普通归纳、强归纳与良序原理的等价性，示范归纳法在算法正确性证明中的用法，并剖析递归与分治的复杂度分析。读完你能写出严谨的归纳证明，也能识别并避免"归纳法滥用"。

一个错得离谱却"证明"了的例子

先看一段伪证："声称所有马的颜色相同。对 n 匹马用归纳法：n = 1 显然；设 n 匹马同色，取 n + 1 匹马，前 n 匹同色、后 n 匹同色，重叠部分传递颜色，故 n + 1 匹同色。"漏洞出在 n = 1 到 n = 2 那一步：两匹马时"前 1 匹"与"后 1 匹"没有重叠，传递性断链。这个伪证的教训比十条注意事项都深刻：归纳基础必须真的接上归纳步骤，中间任何一环断裂，整条无穷链条作废。工程里对应的场景是"边界条件没测"，性质完全同构。

归纳法的严格形式与两个变体

标准归纳法证明的是形如"对一切自然数 n，命题 P 成立"的陈述，两步走：归纳基础验证 P 在起点成立；归纳步骤假设 P 成立（归纳假设），推出 P+1 成立。强归纳法把归纳假设加强为"P 对所有更小的自然数成立"，适合递推依赖多个前项的场景（如证明每个大于 1 的整数有素因子分解——拆掉一个因子后剩下的数可以是任意更小的数，不止小一）。良序原理说"自然数的任意非空子集有最小元"，它与两种归纳法在皮亚诺公理下互相等价。三者关系可以一图记牢：

三种等价形式的互相推导关系

经典例子走一遍完整流程，感受"两行证明无穷命题"的杠杆。命题：前 n 个奇数之和等于 n 的平方。归纳基础：n = 1 时左边 1、右边 1。归纳步骤：设前 n 个奇数之和为 n 的平方，则前 n + 1 个奇数之和等于 n 的平方加上第 n + 1 个奇数（2n + 1），展开恰为 n + 1 的平方。用代码把两边的数值同时验证，直观看到"平方数拆奇数"的结构：

# 命题：1 + 3 + 5 + ... + (2n-1) = n^2
for n in range(1, 8):
    lhs = sum(2 * k - 1 for k in range(1, n + 1))   # 前 n 个奇数之和
    rhs = n ** 2
    assert lhs == rhs, f"n={n} 时命题失效"
    print(f"n={n}: 奇数和={lhs}, 平方={rhs}")
# 输出 n=1..7 全部相等；数值验证不等于证明，但为归纳步骤提供了直观
​

💡 关键直觉：归纳法是"逻辑上的多米诺"，数值验证是"物理上的多米诺"。前者担保无穷，后者只担保有限——两者互补，不能互相替代。

递归定义：归纳的镜像

归纳法自下而上证明，递归定义自上而下定义。阶乘定义为"零的阶乘为一，n 的阶乘为 n 乘以 n 减一的阶乘"，结构与归纳法完全同构：递归基对应归纳基础，递归式对应归纳步骤。计算复杂性理论里，分治算法的分析与归纳如影随形——归并排序"排序 n 个元素"依赖"排序两个 n/2 的子列"，其正确性证明天然是一个强归纳。递归的代价也要算清：

import sys

def fib_naive(n):
    """朴素递归：正确但指数级——同一子问题被反复计算"""
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

def fib_iter(n):
    """迭代版：把递归式展开成状态转移，线性时间常数空间"""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(sys.getrecursionlimit())        # 默认递归深度上限约 1000
print(fib_iter(30), fib_naive(30))    # 两者输出一致：832040
# 朴素版在 n=35 左右开始明显卡顿，子问题重复是罪魁祸首
​

这段代码背后的数学是递推关系的求解：斐波那契的通项可以用第 2 章会讲的特征根方法闭式解出，增长率是黄金比。递归树的高度与宽度共同决定复杂度，这条分析线索在第 5 章算法部分会再展开。

递归定义的另一个绝佳标本是阿克曼函数——一个"全递归函数但非原始递归"的构造。它的增长速度快过任何原始递归函数，直观体验一下：

import sys
sys.setrecursionlimit(100000)

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(2, 3))   # 输出 9，瞬间完成
print(ackermann(3, 3))   # 输出 61，仍很快
# ackermann(4, 2) 的值是 19 位数字，递归调用次数天文级，切勿轻易尝试
# 它证明了一件事：归纳能定义的函数，其"增长能力"可以远超任何固定层级的递归
​

归纳法在算法正确性中的实战

归纳法最有工程价值的舞台是证明循环不变量。以插入排序为例，不变量是"每轮迭代开始时，前 i 个元素已排好序"。归纳基础：i = 1 时单元素天然有序。归纳步骤：第 i 轮把第 i + 1 个元素插入前面有序的 i 个元素中的正确位置，循环体执行后不变量保持，且 i 增一。循环结束时 i 等于数组长度，于是整个数组有序——正确性证明完毕，没有用到任何测试。测试找反例，证明灭反例，这是两者的本质分工。

⚠️ 滥用警戒线：归纳法只适用于以自然数为索引的命题族。"对所有实数 x"不能用普通归纳法直接证（实数不可数，没有"下一个"实数），那是第 3 章极限与连续性的领地，工具换成 epsilon-delta 语言。

本节要点回顾

• 两步结构：归纳基础与归纳步骤缺一不可，"所有马同色"伪证的断点在基础与步骤的衔接处；
• 强归纳允许假设全部更小情形，良序原理与之等价，三者都是皮亚诺归纳公理的化身；
• 递归定义与归纳证明同构：递归基对应归纳基础，递归式对应归纳步骤；
• 循环不变量的归纳证明是算法正确性的标准范式，测试与证明互补而非替代；
• 归纳法的适用边界是以自然数为索引的命题族，连续统命题需要别的武器。

骨架有了，下一节把武器配齐：同一个命题往往有多种证法，选对证法常常是解题效率的分水岭。