数学归纳法

概述

数学归纳法是一种通过基础情形和归纳步骤证明对所有自然数（或足够大的整数）成立的命题的证明方法，是代入法的核心证明工具。

定义

数学归纳法

设 $P (n)$ 是关于自然数 $n$ 的命题。数学归纳法分两步：(1) 基础情形：证明 $P (n_{0})$ 对某个起始值 $n_{0}$ 成立；(2) 归纳步骤：假设 $P (k)$ 成立（归纳假设），证明 $P (k + 1)$ 也成立。

强归纳法：归纳假设中不仅假设 $P (k)$ 成立，而是假设 $P (n_{0}), P (n_{0} + 1), \dots, P (k)$ 全部成立，适用于需要多个较小情形的证明
递归分析中的应用：在代入法中，归纳假设通常为 $T (k) \leq c \cdot g (k)$ （对所有 $k < n$ ），需证明 $T (n) \leq c \cdot g (n)$
减去低阶项：归纳假设中常需包含低阶修正项（如 $c n^{2} - bn$ ），以使归纳步骤中的不等式能够闭合
选择合适的 $c$ 和 $n_{0}$ ：常数 $c$ 需足够大以覆盖基础情形， $n_{0}$ 需足够大以使归纳步骤成立