数学归纳法
shù xué guī nà fǎ
数学归纳法是一种用于证明关于所有自然数的命题的证明技巧,通过证明一个基础情形和一个归纳步骤来完成。
Formula
\text{Prove } P(1); \text{ prove } P(k) \text{ implies } P(k+1)
Definition
数学归纳法是一种证明某个命题对每一个自然数都成立的方法；它有两个步骤：先证明对第一个情形成立，再证明如果对某个数成立，那么它对下一个数也必定成立。严格地说，要证明对所有 $n \ge n_0$ 都有 $P(n)$：先证明基础情形 $P(n_0)$，然后假设 $P(k)$（归纳假设）成立，证明 $P(k+1)$。这等价于 $\mathbb{N}$ 的良序原理（每个非空子集都有最小元素），也等价于皮亚诺第五公理；超限归纳把这一技巧推广到序数，增加了一个极限情形，即若 $P$ 对所有 $\beta < \lambda$ 成立，则 $P(\lambda)$ 也成立。
Example
要证明前 $n$ 个正整数之和为 $n(n+1)/2$：基础情形 $n=1$ 给出 $1 = 1(2)/2 = 1$，归纳步骤假设它对 $k$ 成立，在两边加上 $(k+1)$ 并化简，说明它对 $k+1$ 也成立。要证明对 $n \ge 1$ 有 $2^n > n$：基础情形 $2^1 = 2 > 1$，假设 $2^k > k$，则 $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$。超限归纳法通过在移除孤立点的序数阶段中逐步推进，证明了康托尔-本迪克森定理：$\mathbb{R}$ 中每个闭子集都是一个完备集与一个可数集的并集。
Key Insight
可以把它想成推倒多米诺骨牌：证明第一块会倒下（基础情形），再证明每一块倒下的骨牌都会推倒下一块（归纳步骤），那么所有骨牌都会倒下。归纳法是演绎推理，而非归纳推理，因为你使用的是一条已经证明的蕴含链，而不是根据规律进行猜测；这个名称在历史上其实有点误导。计算机科学中的结构归纳法把同样的原理应用于递归结构（树、列表）而非自然数，从而证明递归数据结构的性质。