数学归纳法

用于证明与自然数有关的命题

逻辑本质是演绎法 ，依据是肯定前件：若 $P \Rightarrow Q$ 成立且 $P$ 真，则 $Q$ 真。

递推步给出 $P_{k} \Rightarrow P_{k + 1}$ ，起始步给出 $P_{1}$ 真，于是 $P_{2}, P_{3}, \dots$ 逐级传递，命题对所有 $n$ 成立。两步缺一不可：起点不真则骨牌效应无法启动。

第一数学归纳法

起始步： $5^{1} + 3 = 8 = 4 \times 2$
递推步：设 $5^{k} + 3 = 4 q$ （ $q$ 为整数）
$5^{k + 1} + 3 = 5 \cdot 5^{k} + 15 - 12 = 5 (5^{k} + 3) - 12 = 5 \cdot 4 q - 4 \cdot 3 = 4 (5 q - 3)$
结论： $5 q - 3$ 为整数，故 $5^{k + 1} + 3$ 是 $4$ 的倍数

技巧：加 15 再减 15，凑出归纳假设 $5^{k} + 3$ 的结构。假设的表达式是递推步的核心。

$x_{1} = 2$ ， $x_{n} = 4 - \frac{1}{1 + x _{n - 1}}$ ，证 ${x_{n}}$ 单调增加，即证 $x_{n} > x_{n - 1} (n \geq 2)$ 。

起始步： $x_{2} = 4 - \frac{1}{1 + 2} = \frac{11}{3} > x_{1}$
递推步：设 $x_{k} > x_{k - 1}$ ，由数列正向
$x_{k + 1} = 4 - \frac{1}{1 + x _{k}} > 4 - \frac{1}{1 + x _{k - 1}} = x_{k}$
结论： $x_{k + 1} > x_{k}$ ，故 $x_{n} > x_{n - 1} (n \geq 2)$ ，数列单调增加

与第一类唯一区别：归纳假设加强为 $n \leq k$ 时命题均成立，再推 $n = k + 1$ 。

适用：递推式同时依赖前若干项（如含 $a_{n}$ 与 $a_{n - 1}$ ）时必须用第二类。

$a_{0} = 1$ ， $a_{1} = 0$ ， $a_{n + 1} = \frac{n a _{n} + a _{n - 1}}{n + 1}$ ，证 $0 \leq a_{n} \leq 1$ 。

起始步： $a_{0, 1} = 1 \in [0, 1]$
递推步：设 $0 \leq a_{n} \leq 1 (n \leq k)$ ，则 $a_{k}, a_{k - 1} \in [0, 1]$
$0 \leq a_{k + 1} = \frac{k a _{k} + a _{k - 1}}{k + 1} \leq \frac{k \cdot 1 + 1}{k + 1} = 1$
结论： $0 \leq a_{k + 1} \leq 1$ ，故 $0 \leq a_{n} \leq 1 (n \geq 0)$

$a_{1} = 1$ ， $a_{2} = 2$ ， $a_{n} = a_{n - 1} + a_{n - 2}$ ，证 $0 \leq a_{n} \leq 2^{n - 1} (n \geq 1)$ 。

起始步： $a_{1} = 1 \leq 2^{0}$
递推步：设 $0 \leq a_{n} \leq 2^{n - 1} (n \leq k)$
$a_{k + 1} = a_{k} + a_{k - 1} \leq 2^{k - 1} + 2^{k - 2} < 2 \cdot 2^{k - 1} = 2^{k}$
结论： $0 \leq a_{k + 1} \leq 2^{k}$ ，故 $0 \leq a_{n} \leq 2^{n - 1} (n \geq 1)$

命题 ” $7 n + 2$ 恒为 7 的倍数” 为假，但递推步看似可证：设 $7 k + 2 = 7 q$ ，则

$7 (k + 1) + 2 = (7 k + 2) + 7 = 7 q + 7 = 7 (q + 1)$

而 $n = 1$ 时 $7 + 2 = 9$ 不是 7 的倍数——起点即假，递推再顺也无意义。

① 写出归纳假设；

② 由假设推 $k + 1$ ；

③ 验证起始项；

④ 综上命题成立。

大题空间有限，用简化写法（省去文字，只留关键式子）：

第一类： $x_{2} = \frac{11}{3} > x_{1}$ ；设 $x_{k} > x_{k - 1}$ ； $x_{k + 1} = 4 - \frac{1}{1 + x _{k}} > 4 - \frac{1}{1 + x _{k - 1}} = x_{k}$

故 $x_{n} > x_{n - 1} (n \geq 2)$
第二类： $a_{0, 1} = 1 \in [0, 1]$ ；设 $0 \leq a_{n} \leq 1 (n \leq k)$ ； $a_{k + 1} = \frac{k a _{k} + a _{k - 1}}{k + 1} \leq 1$ ，

故 $0 \leq a_{n} \leq 1 (n \geq 0)$