数学归纳法 | 杨星宇

数学归纳法通过把基础情形和归纳步骤连接起来，证明某个范围内的每个整数都满足目标命题。它特别适合处理递归定义、求和公式和算法性质。

归纳原理

定理数学归纳原理

设 $P(n)$ 是每个整数 $n\ge n_0$ 对应的命题。如果

那么对每个 $n\ge n_0$ ， $P(n)$ 都为真。

基础情形启动这条链，归纳步骤说明真值如何从一个下标传递到下一个下标。两部分缺一不可。

例前 $n$ 个正整数之和

证明对每个 $n\ge1$ ，

1+2+\cdots+n=\frac{n(n+1)}{2}

证明

当 $n=1$ 时，两边都等于 $1$ 。假设公式对 $n=k$ 成立，则

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{(k+1)(k+2)}{2} \end{aligned}

这正是下标为 $k+1$ 时的公式，所以归纳法证明了结论。

强归纳法在归纳步骤中假设从 $n_0$ 到 $k$ 的所有命题都成立，而不是只假设 $P(k)$ 。如果这些假设能推出 $P(k+1)$ ，同样可以完成归纳。

定理强归纳原理

设 $P(n)$ 对每个 $n\ge n_0$ 定义。如果 $P(n_0)$ 为真，并且对每个 $k\ge n_0$ ，

P(n_0),P(n_0+1),\ldots,P(k)

共同推出 $P(k+1)$ ，那么 $P(n)$ 对每个 $n\ge n_0$ 都为真。

当递归算法或分解论证需要多个较小规模的结果时，强归纳法尤其有用。

例前 $n$ 个奇数之和

对每个 $n\ge1$ ，都有

1+3+5+\cdots+(2n-1)=n^2

证明

当 $n=1$ 时结论成立。若公式对 $n=k$ 成立，则

1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2

因此归纳步骤成立，结论对所有 $n\ge1$ 成立。

写归纳证明时，应明确起始下标，并把基础情形、归纳假设和归纳步骤分开。归纳步骤中先写出 $k+1$ 的目标表达式，再调用归纳假设，更容易发现下标错位或漏项。