数据结构与算法 / 系统课时
数学归纳法
数学归纳法
若一个性质要对所有自然数规模成立,可以先证明起始规模,再证明成立的性质如何传到下一规模。本课将普通和强归纳用于求和、素数分解与递归阶乘。
学习目标
- 给出定义域、基础情形、归纳假设与递推一步的完整论证。
- 说明普通归纳与强归纳何时更方便。
- 将递归正确性和终止理由分开,并核对实际解释器限制。
从起点到下一步
要证明 对每个整数 成立,先证明 。归纳步骤任取整数 ,在假设 的条件下推导 。任意的 与起点共同保证证明链覆盖整个定义域。若递推依赖多个前驱,可以用多个基础情形和相应的归纳假设。 MIT《计算机科学的数学》归纳法

以 为例,可从 开始。空和为 0,两边相等。假设前 项和为 ,加上 得 ,正好是下一规模的公式。
强归纳法
在证明 时,可以假设从 到 都成立。比如证明每个大于等于 2 的整数都能写成素数乘积,基础情形 2 本身是素数。若目标整数 是素数,单个因子就满足结论;若是合数,可写成 ,其中 。归纳假设分别给出 的素数分解,相乘得到目标分解。这里仅证明存在性,唯一性需要另外论证。
强归纳和普通归纳可相互表达。把“从起点到 的性质都成立”作为新命题,就能用普通归纳维护整段性质。 MIT《计算机科学的数学》强归纳
用归纳证明递归阶乘
对内建非负整数 ,阶乘定义为 ,并且当 时 。如下实现以 0 为唯一递归基础。数学算法每次把正整数规模减 1,有限步后到 0。证明正确性时,基础情况直接返回 1;若规模 的调用返回 ,规模 的返回值就是 。
把下面代码保存为 factorial_demo.py,使用本教程的 Python 3.11 或以上运行。标准库的 math.factorial 用来交叉检查 0 到 5。
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}")0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120此实现对规模 执行 次乘法,递归调用的栈深度随 线性增长。将乘法当单位操作时,可说执行步骤与 同阶。实际整数位数会增长,乘法和结果存储成本不能只按调用次数估计。Python 还有递归深度上限,大输入可能在到达基础情形前触发 RecursionError。证明覆盖的是理想递推;实际运行还受资源限制。处理较大整数可用迭代或标准库,而不要为了此示例提高解释器递归限制。 Python 递归深度 Python math.factorial
本课练习
证明前 个正奇数之和为 ,写明是否从空和开始。再为斐波那契递推列出两个基础情形和需要的前驱假设。下一课用同样的推理结构证明循环正确性。