1. 第一数学归纳法
设 $P(n)$ 表示一个与自然数 $n$ 有关的命题,若
- $P(n_0)$($n_0 \in \mathbb{N}$)成立;
- 假设 $P(k)$($k\geq n_0$)成立,可推出 $P(k+1)$ 成立,
则 $P(n)$ 对一切自然数 $n\ge n_0$,$n\in \mathbb{N}$ 都成立。
2. 第二数学归纳法
设 $P(n)$ 表示一个与自然数 $n$ 有关的命题,若
- $P(n_0)$($n_0 \in \mathbb{N}$)成立;
- 假设 $P(n)$ 在 $n_0 \le n \le k$ 时成立,可推出 $P(k+1)$ 成立,
则 $P(n)$ 对一切自然数 $n\ge n_0$,$n\in \mathbb{N}$ 时都成立。
3. 逆向归纳法(亦称倒推归纳法或向前-向后归纳法)
- 第 1 步:运用通常的归纳法证明命题 $P(n)$ 对自然数的某个子序列 ${n_k}$ 成立,即 $P(n_k)$ 成立($n_k \to + \infty$).
- 第 2 步:$P(n)$ 成立可以推出 $P(n-1)$ 成立,
则对于一切自然数 $n$,$P(n)$ 成立.
例题1:设 $a_1, a_2, \cdots, a_n \in \mathbb{R}^+$,$A_n = \frac{1}{n} (a_1 + a_2 + \cdots + a_n)$,$G_n = \sqrt[^n]{(a_1a_2\cdots a_n)}$,求证:$A_n \geq G_n$ (等号成立当且仅当 $a_1=a_2=\cdots = a_n$ 时成立)。
【证明】先证对一切 $n = 2^m$($m \in \mathbb{N}$),$A_n \geq G_n$ 成立,为此对 $m$ 使用归纳法。
当 $m=1$ 时,有:
$$A_2 = \frac{1}{2} (a_1 + a_2) = \frac{1}{2} (\sqrt{a_1} - \sqrt{a_2})^2 + \sqrt{a_1a_2} \geq \sqrt{a_1a_2} = G_2$$
等号当且仅当 $a_1 = a_2$ 时成立。即 $m=1$ 时,$A_{2^m} \geq G_{2^m}$ 成立。
假设当 $m=k \in \mathbb{N}$ 时,不等式成立,即 $A_{2^k} \geq G_{2^k}$。于是,当 $m = k+1$ 时有:
$$
所以,对一切 $n=2^m$ ($m=1,2,\cdots$),$A_{2^m} \geq G_{2^m}$ 成立。接着证明,如果对于任意的 $k \in \mathbb{N}$,$A_k \ge G_k$ 成立,那么 $A_{k-1} \ge G_{k-1}$ 也成立。
事实上,我们令 $a_k = \frac 1 {k-1} (a_1 + a_2 + \ldots + a_{k-1})$,则
故而 $A_{k-1}^k \ge (G_{k-1})^{k-1} A_{k-1}$,即 $A_{k-1} \ge G_{k-1}$ 成立。
由逆向归纳法知,命题成立。
4 跳跃数学归纳法
设 $P(n)$ 表示一个与自然数 $n$ 有关的命题,若
- $P(m)$($1\le m \le t$)成立;
- 假设 $P(k)$ 成立,可推出 $P(k+t)$ 成立,
则 $P(n)$ 对一切自然数 $n$ 都成立。
5 螺旋归纳法
设 $P(n)$ 和 $Q(n)$ 是两串与自然数 $n$ 有关的命题,如果
(1) 命题 $P(1)$ 成立;
(2) 对于 $k \in \mathbb{N}$,若命题 $P(k)$ 成立,则命题 $Q(k)$ 成立,若命题 $Q(k)$ 成立,则命题 $P(k+1)$ 成立,
则对于所有自然数 $n$,命题 $P(n)$ 与 $Q(n)$ 都成立.