数据结构与算法 / 系统课时

数学归纳法

数学归纳法

若一个性质要对所有自然数规模成立,可以先证明起始规模,再证明成立的性质如何传到下一规模。本课将普通和强归纳用于求和、素数分解与递归阶乘。

学习目标

  • 给出定义域、基础情形、归纳假设与递推一步的完整论证。
  • 说明普通归纳与强归纳何时更方便。
  • 将递归正确性和终止理由分开,并核对实际解释器限制。

从起点到下一步

要证明 P(n)P(n) 对每个整数 n≥n0n≥n_0 成立,先证明 P(n0)P(n_0)。归纳步骤任取整数 k≥n0k≥n_0,在假设 P(k)P(k) 的条件下推导 P(k+1)P(k+1)。任意的 kk 与起点共同保证证明链覆盖整个定义域。若递推依赖多个前驱,可以用多个基础情形和相应的归纳假设。 MIT《计算机科学的数学》归纳法

数学归纳法证明链路

以 1+2+…+n=n(n+1)/21+2+…+n=n(n+1)/2 为例,可从 n=0n=0 开始。空和为 0,两边相等。假设前 kk 项和为 k(k+1)/2k(k+1)/2,加上 k+1k+1 得 k(k+1)/2+(k+1)=(k+1)(k+2)/2k(k+1)/2+(k+1)=(k+1)(k+2)/2,正好是下一规模的公式。

强归纳法

在证明 P(k+1)P(k+1) 时,可以假设从 P(n0)P(n_0) 到 P(k)P(k) 都成立。比如证明每个大于等于 2 的整数都能写成素数乘积,基础情形 2 本身是素数。若目标整数 k+1k+1 是素数,单个因子就满足结论;若是合数,可写成 abab,其中 2≤a,b≤k2≤a,b≤k。归纳假设分别给出 a,ba,b 的素数分解,相乘得到目标分解。这里仅证明存在性,唯一性需要另外论证。

强归纳和普通归纳可相互表达。把“从起点到 kk 的性质都成立”作为新命题,就能用普通归纳维护整段性质。 MIT《计算机科学的数学》强归纳

用归纳证明递归阶乘

对内建非负整数 nn,阶乘定义为 0!=10!=1,并且当 n>0n>0 时 n!=n(n−1)!n!=n(n-1)!。如下实现以 0 为唯一递归基础。数学算法每次把正整数规模减 1,有限步后到 0。证明正确性时,基础情况直接返回 1;若规模 kk 的调用返回 k!k!,规模 k+1k+1 的返回值就是 (k+1)k!=(k+1)!(k+1)k!=(k+1)!。

把下面代码保存为 factorial_demo.py,使用本教程的 Python 3.11 或以上运行。标准库的 math.factorial 用来交叉检查 0 到 5。

python
import math


def factorial(n: int) -> int:
    if type(n) is not int:
        raise TypeError("n must be a built-in int")
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)


if __name__ == "__main__":
    for n in range(6):
        result = factorial(n)
        assert result == math.factorial(n)
        print(f"{n}! = {result}")
text
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

此实现对规模 nn 执行 nn 次乘法,递归调用的栈深度随 nn 线性增长。将乘法当单位操作时,可说执行步骤与 nn 同阶。实际整数位数会增长,乘法和结果存储成本不能只按调用次数估计。Python 还有递归深度上限,大输入可能在到达基础情形前触发 RecursionError。证明覆盖的是理想递推;实际运行还受资源限制。处理较大整数可用迭代或标准库,而不要为了此示例提高解释器递归限制。 Python 递归深度 Python math.factorial

本课练习

证明前 nn 个正奇数之和为 n2n^2,写明是否从空和开始。再为斐波那契递推列出两个基础情形和需要的前驱假设。下一课用同样的推理结构证明循环正确性。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

数学归纳法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通