Appearance
数学归纳法
数学归纳法（Mathematical Induction）是数学竞赛中最核心的证明工具之一。它基于皮亚诺公理中的归纳原理，将"无穷"的验证转化为"有限"的推理。
第一数学归纳法
基本原理
第一数学归纳法
设 $P(n)$是关于自然数$n$ 的命题，若：
- 奠基步骤：$P(n_0)$ 成立（$n_0$ 为起始自然数）；
- 归纳步骤：对任意 $k \geq n_0$，若 $P(k)$成立，可推出$P(k+1)$ 成立；
则 $P(n)$对所有$n \geq n_0$ 均成立。
这个原理可用多米诺骨牌来理解：推倒第一张牌，且每张牌倒下会使下一张倒下，则所有牌依次倒下。
标准步骤与写法
竞赛中归纳法证明的标准格式：
- 明确陈述命题 $P(n)$；
- 当 $n=n_0$时，验证$P(n_0)$ 成立；
- 假设 $n=k$时$P(k)$ 成立（归纳假设）；
- 证明 $n=k+1$时$P(k+1)$ 也成立；
- 由数学归纳法，$P(n)$对所有$n \geq n_0$ 成立。
归纳奠基的选择技巧
奠基不一定从 $n=1$开始。例如证明$n^2 < 2^n$ 时，$n=1,2,3,4$均不成立，应从$n=5$ 开始奠基。有些命题的递推依赖于多个初始值，奠基需要多步。
奠基选择
先尝试小 $n$验证命题是否成立，找到第一个使命题成立的自然数作为奠基。若递推涉及前两项，则奠基需验证$n=n_0$和$n=n_0+1$ 两项。
例题
例题1 证明：$1+2+3+\cdots+n = \dfrac{n(n+1)}{2}$。
解析：设 $P(n)$ 为上述等式。
（1）奠基：$n=1$时，左边$=1$，右边 $=\frac{1\cdot 2}{2}=1$，$P(1)$ 成立。
（2）归纳：假设 $P(k)$成立，即$1+2+\cdots+k = \frac{k(k+1)}{2}$。则当 $n=k+1$ 时： $$1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2},$$ 即 $P(k+1)$成立。由归纳法，等式对所有正整数$n$ 成立。
例题2 证明：对任意正整数 $n$，$n^3+5n$能被$6$ 整除。
解析：$P(n)$：$n^3+5n \equiv 0 \pmod 6$。
奠基：$n=1$ 时，$1^3+5=6$，成立。
归纳：设 $P(k)$成立，即$k^3+5k = 6m$。则 $$\begin{aligned} (k+1)^3+5(k+1) &= (k^3+3k^2+3k+1) + (5k+5) \newline &= (k^3+5k) + 3k^2+3k+6 \newline &= 6m + 3k(k+1) + 6. \end{aligned}$$ 由于 $k(k+1)$为两连续整数之积，必为偶数，故$3k(k+1)$是$6$的倍数。因此$P(k+1)$ 成立。由归纳法，原命题成立。
例题3 证明：$1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}$。
解析：奠基 $n=1$显然。假设$P(k)$ 成立，则 $$1^2+2^2+\cdots+k^2+(k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$$ $$= \frac{k+1}{6}[k(2k+1)+6(k+1)] = \frac{k+1}{6}(2k^2+7k+6) = \frac{(k+1)(k+2)(2k+3)}{6}.$$ 即 $P(k+1)$ 成立。由归纳法得证。
第二数学归纳法（强归纳法）
基本原理
第二数学归纳法
设 $P(n)$是关于自然数$n$ 的命题，若：
- $P(n_0)$ 成立；
- 对任意 $k \geq n_0$，若 $P(n_0), P(n_0+1), \ldots, P(k)$全部成立，可推出$P(k+1)$ 成立；
则 $P(n)$对所有$n \geq n_0$ 均成立。
与第一归纳法的区别与联系
第一归纳法只需 $P(k)$这一个假设推出$P(k+1)$；第二归纳法需要假设从奠基到 $k$的所有命题都成立来推出$P(k+1)$。第二归纳法包含了第一归纳法；二者在逻辑上等价，但第二归纳法在某些问题上更自然。
适用场景
- 递推数列：递推关系中涉及不止前一项时（如 Fibonacci 数列 $F_{n}=F_{n-1}+F_{n-2}$），需要前两项作为归纳假设；
- 数论问题：证明涉及质因数分解、整除性等——$n$ 的性质可能依赖于其所有真因子的性质；
- 组合拆分：将 $n$ 拆分为若干较小部分，每个部分的性质由归纳假设保证。
例题
例题4（Fibonacci 数列）已知 $F_1=F_2=1$，$F_{n}=F_{n-1}+F_{n-2}$（$n \geq 3$）。证明： $$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].$$
解析：用第二归纳法。奠基：$n=1,2$ 分别验证。
归纳：假设对所有 $m \leq k$（$k \geq 2$）公式成立，则 $$F_{k+1} = F_k + F_{k-1} = \frac{1}{\sqrt{5}}\left(\alpha^k - \beta^k\right) + \frac{1}{\sqrt{5}}\left(\alpha^{k-1} - \beta^{k-1}\right)$$ $$= \frac{1}{\sqrt{5}}\left[\alpha^{k-1}(\alpha+1) - \beta^{k-1}(\beta+1)\right].$$ 由 $\alpha = \frac{1+\sqrt{5}}{2}$满足$\alpha^2=\alpha+1$，得 $\alpha+1=\alpha^2$，同理 $\beta+1=\beta^2$，因此 $$F_{k+1} = \frac{1}{\sqrt{5}}\left(\alpha^{k+1} - \beta^{k+1}\right).$$ $P(k+1)$成立。由第二归纳法，通项公式对所有正整数$n$ 成立。
例题5 证明：任一大于 $1$的整数$n$ 可分解为质数的乘积。
解析：$P(n)$：$n$ 可表为质数之积。
奠基：$n=2$ 为质数，显然成立。
归纳：假设对所有 $m$满足$2 \leq m \leq k$，$P(m)$成立。考虑$n=k+1$。若 $k+1$为质数，则$P(k+1)$成立。若$k+1$为合数，则$k+1 = ab$，其中 $2 \leq a,b \leq k$。由归纳假设，$a$和$b$均可分解为质数之积，故$k+1$ 亦然。由第二归纳法得证。
思考
此题若用第一归纳法，归纳假设只有 $P(k)$，但 $k+1$的因子$a,b$不一定等于$k$，无法直接使用 $P(k)$。这正是第二归纳法优于第一归纳法的典型场景。
跳跃归纳法
基本原理
跳跃归纳法
设步长为 $d$（正整数），若：
- $P(n_0), P(n_0+1), \ldots, P(n_0+d-1)$这$d$ 个基础情形均成立；
- 对任意 $k \geq n_0$，$P(k) \Rightarrow P(k+d)$；
则 $P(n)$对所有$n \geq n_0$ 成立。
相当于将自然数分成 $d$ 个同余类，每类独立归纳。
例题
例题6 证明：对任意正整数 $n$，$2^n+1$在$n$为奇数时能被$3$ 整除。
解析：$P(n)$：$n$为奇数时$3 \mid 2^n+1$。
奠基：$n=1$，$2^1+1=3$，成立。
归纳（步长 $d=2$）：假设 $P(k)$ 成立（$k$为奇数），即$2^k+1=3m$。则 $$2^{k+2}+1 = 4 \cdot 2^k + 1 = 4(3m-1) + 1 = 12m - 3 = 3(4m-1),$$ 故 $P(k+2)$成立。由跳跃归纳法（步长$2$，只涉及奇数），原命题对所有奇数 $n$ 成立。
例题7 证明：$\cos \dfrac{\pi}{2^n}$ 可表示为嵌套平方根形式。
解析：用步长 $d=1$的标准归纳法。已知$\cos\frac{\pi}{4}=\frac{\sqrt{2}}{2}$，且由半角公式 $\cos\frac{\theta}{2} = \sqrt{\frac{1+\cos\theta}{2}}$，命题自然归纳。
反向归纳法（柯西归纳法）
基本原理
反向归纳法
设 $P(n)$是关于自然数$n$ 的命题，若：
- $P(n)$对无穷多个$n$（通常是 $n=2^k$）成立；
- $P(n) \Rightarrow P(n-1)$（从大到小反向递推）；
则 $P(n)$对所有充分大的$n$ 成立（通常可覆盖所有正整数）。
经典应用：AM-GM 不等式的柯西证明
例题8（柯西证明）证明 $n$ 个正数的算术-几何平均不等式： $$\frac{a_1+a_2+\cdots+a_n}{n} \geq \sqrt[n]{a_1 a_2 \cdots a_n}.$$
解析：$P(n)$ 为上述不等式。
第1步：证明 $P(2)$。即 $\frac{a_1+a_2}{2} \geq \sqrt{a_1 a_2}$，由 $(\sqrt{a_1}-\sqrt{a_2})^2 \geq 0$ 即得。
第2步：$P(k) \Rightarrow P(2k)$。将 $2k$个数分成两组各$k$ 个： $$\begin{aligned} \frac{a_1+\cdots+a_{2k}}{2k} &= \frac{\frac{a_1+\cdots+a_k}{k} + \frac{a_{k+1}+\cdots+a_{2k}}{k}}{2} \newline &\geq \frac{\sqrt[k]{a_1\cdots a_k} + \sqrt[k]{a_{k+1}\cdots a_{2k}}}{2} \quad \text{(由 } P(k) \text{)} \newline &\geq \sqrt{\sqrt[k]{a_1\cdots a_k} \cdot \sqrt[k]{a_{k+1}\cdots a_{2k}}} \quad \text{(由 } P(2) \text{)} \newline &= \sqrt[2k]{a_1\cdots a_{2k}}. \end{aligned}$$ 因此 $P(2) \Rightarrow P(4) \Rightarrow P(8) \Rightarrow \cdots$，即 $P(2^m)$对所有$m$ 成立。
第3步：$P(n) \Rightarrow P(n-1)$。对于 $n-1$个正数，令$a_n = \frac{a_1+\cdots+a_{n-1}}{n-1}$，代入 $P(n)$即得$P(n-1)$。
综上，$P(n)$对所有正整数$n$ 成立。这一证明精巧地结合了正向和反向归纳。
柯西归纳法的精髓
核心思路：先证 $2^k$的情形（正向加倍），再反向收缩到任意$n$。适用于"均值"类不等式，因为 $2^k$ 情形可自然地两两分组。
螺旋归纳法
基本原理
螺旋归纳法
设有 $m$个命题$P_1(n), P_2(n), \ldots, P_m(n)$，若存在一个循环推理链： $$P_1(k) \Rightarrow P_2(k) \Rightarrow \cdots \Rightarrow P_m(k) \Rightarrow P_1(k+1),$$ 且奠基 $P_1(n_0), \ldots, P_m(n_0)$均成立，则所有命题对所有$n \geq n_0$ 成立。
这相当于将多个命题"编织"在一起归纳。
例题
例题9 设数列 $\lbrace a_n\rbrace $满足$a_1=1$，$a_{2n}=a_n$，$a_{2n+1}=a_n+a_{n+1}$。证明：$a_n \leq n$对所有正整数$n$ 成立。
解析：定义两个命题：
- $P(n)$：$a_n \leq n$；
- $Q(n)$：$a_{n+1} \leq n+1$。
奠基：$a_1=1 \leq 1$，$P(1)$ 成立；$a_2 = a_1 = 1 \leq 2$，$Q(1)$ 成立。
归纳螺旋：
- $P(k)$和$Q(k)$成立$\Rightarrow a_{2k+1} = a_k + a_{k+1} \leq k + (k+1) = 2k+1$，得 $P(2k+1)$；
- 再结合可得 $a_{2k+2} = a_{k+1} \leq k+1 \leq 2k+2$，得 $Q(2k+1)$。
通过螺旋推理，$a_n \leq n$对所有$n$ 成立（形式化需结合强归纳或处理所有奇偶分支）。
螺旋归纳的应用
螺旋归纳在递推同时涉及奇偶分支时非常有用，可视为将复杂递推分解为多条轨道分别归纳。
归纳法在竞赛中的应用
证明通项公式
例题10 数列 $\lbrace a_n\rbrace $满足$a_1=1$，$a_{n+1}=2a_n+1$，求通项并证明。
解析：先求不动点 $x=2x+1 \Rightarrow x=-1$。令 $b_n=a_n+1$，则 $b_1=2$，$b_{n+1}=2b_n$，故 $b_n=2^n$，猜想 $a_n=2^n-1$。
归纳证明：奠基 $n=1$成立。假设$a_k=2^k-1$，则 $a_{k+1}=2(2^k-1)+1=2^{k+1}-1$。证毕。
证明不等式
例题11（Bernoulli 不等式）证明对 $x>-1$且$x \neq 0$，正整数 $n \geq 2$时有$(1+x)^n > 1+nx$。
解析：奠基 $n=2$：$(1+x)^2 = 1+2x+x^2 > 1+2x$，成立。
归纳：假设 $(1+x)^k > 1+kx$。则 $$(1+x)^{k+1} = (1+x)^k(1+x) > (1+kx)(1+x) = 1+(k+1)x + kx^2 > 1+(k+1)x.$$ 证毕。
不等式归纳的注意点
不等式归纳时，放缩方向必须严格一致。引入的中间量要确保不等号方向正确。若 $x$可能为负，乘$(1+x)$时需注意$(1+x)$的符号——本题中$x>-1$保证了$1+x>0$。
证明整除性
例题12 证明：对任意正整数 $n$，$4^{n+1}+5^{2n-1}$能被$21$ 整除。
解析：奠基 $n=1$：$4^2+5^1=16+5=21$，成立。
归纳：设 $4^{k+1}+5^{2k-1}=21m$。则 $$\begin{aligned} 4^{k+2}+5^{2k+1} &= 4 \cdot 4^{k+1} + 25 \cdot 5^{2k-1} \newline &= 4 \cdot 4^{k+1} + (4+21) \cdot 5^{2k-1} \newline &= 4(4^{k+1}+5^{2k-1}) + 21 \cdot 5^{2k-1} \newline &= 4 \cdot 21m + 21 \cdot 5^{2k-1} = 21(4m+5^{2k-1}). \end{aligned}$$ $P(k+1)$ 成立。由归纳法，原命题成立。
证明组合恒等式
例题13 证明 $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n$。
解析：奠基 $n=0$：$\binom{0}{0}=1=2^0$，成立。
归纳：假设 $\sum_{k=0}^{n}\binom{n}{k}=2^n$。利用 $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$： $$\sum_{k=0}^{n+1}\binom{n+1}{k} = \sum_{k=0}^{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right] = \sum_{k=0}^{n}\binom{n}{k} + \sum_{k=0}^{n}\binom{n}{k} = 2^n+2^n = 2^{n+1}.$$ （其中约定 $\binom{n}{-1}=\binom{n}{n+1}=0$。）证毕。
证明几何命题
例题14 证明：$n$条直线最多将平面分成$\dfrac{n(n+1)}{2}+1$ 个区域。
解析：$n=1$ 时，$1$条直线分平面为$2 = \frac{1\cdot 2}{2}+1$ 个区域，成立。
假设 $k$条直线最多分$\frac{k(k+1)}{2}+1$个区域。添加第$k+1$条直线，与之前$k$条直线最多交于$k$个点，将第$k+1$条直线分成$k+1$段，每段将原有区域一分为二，故新增$k+1$ 个区域。 $$f(k+1) = f(k)+(k+1) = \frac{k(k+1)}{2}+1+(k+1) = \frac{(k+1)(k+2)}{2}+1.$$ 由归纳法，公式对所有 $n$ 成立。
归纳构造法
归纳法不仅用于证明，还可用于构造满足特定性质的对象。其核心思想是：假设已构造出规模为 $k$的对象，以此为基础构造规模为$k+1$ 的对象。
归纳构造的范式
- 给出小规模 $n_0$ 的构造作为基础；
- 描述如何从规模 $k$的构造扩展为规模$k+1$ 的构造；
- 验证扩展后的构造满足所有要求。
例题15（图论）证明：任意 $n$个顶点的树（无环连通图）恰有$n-1$ 条边。
解析：对顶点数 $n$ 归纳。
奠基：$n=1$，单点树有 $0$ 条边，$0=1-1$，成立。
归纳：假设 $n=k$时成立。考虑$n=k+1$个顶点的树$T$。树必存在叶子（度数为 $1$的顶点）。删除该叶子及其关联边，得到$k$个顶点的树$T'$。由归纳假设，$T'$有$k-1$条边，故$T$有$(k-1)+1=k$ 条边。$k=(k+1)-1$，命题成立。
精选例题
例题16 证明：$\displaystyle\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}$。
解析：奠基 $n=1$：$\frac{1}{1\cdot 2}=\frac{1}{2}$，成立。
归纳：假设 $\sum_{k=1}^{m}\frac{1}{k(k+1)}=\frac{m}{m+1}$，则 $$\sum_{k=1}^{m+1}\frac{1}{k(k+1)} = \frac{m}{m+1} + \frac{1}{(m+1)(m+2)} = \frac{m(m+2)+1}{(m+1)(m+2)} = \frac{(m+1)^2}{(m+1)(m+2)} = \frac{m+1}{m+2}.$$ 证毕。
例题17 证明：对正整数 $n$，$1+3+5+\cdots+(2n-1)=n^2$。
解析：$n=1$：$1=1^2$。假设 $1+3+\cdots+(2k-1)=k^2$，则 $$1+3+\cdots+(2k-1)+(2k+1)=k^2+(2k+1)=(k+1)^2.$$ 证毕。
例题18（IMO 经典）证明：对任意正整数 $n$，$\displaystyle\sum_{k=1}^{n}\frac{1}{k^2} < 2$。
解析：加强命题：证明 $\sum_{k=1}^{n}\frac{1}{k^2} \leq 2-\frac{1}{n}$。
奠基 $n=1$：$1 \leq 2-1=1$，成立。
归纳：假设 $\sum_{k=1}^{m}\frac{1}{k^2} \leq 2-\frac{1}{m}$，则 $$\sum_{k=1}^{m+1}\frac{1}{k^2} \leq 2-\frac{1}{m} + \frac{1}{(m+1)^2}.$$ 只需证 $2-\frac{1}{m}+\frac{1}{(m+1)^2} \leq 2-\frac{1}{m+1}$，即 $\frac{1}{(m+1)^2} \leq \frac{1}{m}-\frac{1}{m+1}=\frac{1}{m(m+1)}$，等价于 $(m+1)^2 \geq m(m+1)$，显然成立。证毕。
加强命题的技巧
当原命题不易直接归纳时，可考虑加强命题，使归纳假设更强，从而归纳步骤更易通过。上题中直接归纳 $\sum 1/k^2 < 2$会卡住，加强为$2-1/n$ 后顺利通过。
例题19 证明：$n$个不同元素的全排列数为$n!$。
解析：$n=1$显然。假设$k$个元素有$k!$种排列。第$k+1$个元素可插入$k$个元素排列的$k+1$个空隙中，故排列数为$(k+1) \cdot k! = (k+1)!$。证毕。
例题20 设 $a_1=2$，$a_{n+1}=a_n^2-a_n+1$。证明：对任意 $n$，$a_n$与$a_{n+1}$ 互质。
解析：奠基 $n=1$：$a_1=2$，$a_2=2^2-2+1=3$，$\gcd(2,3)=1$。
归纳：假设 $\gcd(a_k, a_{k+1})=1$。注意到 $$a_{k+2} = a_{k+1}^2 - a_{k+1} + 1 = a_{k+1}(a_{k+1}-1) + 1.$$ 而 $a_{k+1}-1 = a_k^2-a_k = a_k(a_k-1)$。若 $d \mid a_{k+1}$且$d \mid a_{k+2}$，则 $d \mid a_{k+2}-a_{k+1}(a_{k+1}-1)=1$，故 $\gcd(a_{k+1},a_{k+2})=1$。证毕。
例题21 证明：对任意正整数 $n$，$n^5-n$能被$30$ 整除。
解析：$n=1$：$1^5-1=0$，成立。假设 $k^5-k=30m$。则 $$\begin{aligned} (k+1)^5-(k+1) &= (k^5+5k^4+10k^3+10k^2+5k+1) - (k+1) \newline &= (k^5-k) + 5k(k^3+2k^2+2k+1) \newline &= 30m + 5k(k+1)(k^2+k+1). \end{aligned}$$ $k(k+1)$为偶数，故$5k(k+1)$被$10$整除；再验证整体被$3$ 整除，综合得证。
例题22（托布利兹猜想）用归纳法证明：若将 $1,2,\ldots,2n$任意分成两组各$n$个数，则必有一组中存在两个数之和为完全平方数。对$n=1,2,\ldots$ 验证。
解析（简略）：对 $n$归纳，利用$2n-1$和$2n$ 的配对性质，结合归纳假设即可。此题体现了归纳法在组合存在性问题中的应用。
例题23 证明：$n$阶完全图$K_n$的边数恰为$\binom{n}{2}$。
解析：奠基 $n=2$：$K_2$有$1$ 条边，$\binom{2}{2}=1$。
归纳：假设 $K_k$有$\binom{k}{2}$ 条边。$K_{k+1}$比$K_k$多一个顶点，该顶点与$K_k$的$k$ 个顶点各连一条边，故 $$E(K_{k+1}) = \binom{k}{2} + k = \frac{k(k-1)}{2} + k = \frac{k(k+1)}{2} = \binom{k+1}{2}.$$ 证毕。
常见错误与注意事项
错误1：归纳假设使用不当
在归纳步骤中，假设 $P(k)$成立后，不能直接说"同理$P(k+1)$成立"。必须写出从$P(k)$到$P(k+1)$ 的推导过程。有些题目中，归纳假设的条件和结论需要仔细区分，避免循环论证。
错误2：奠基步骤遗漏
多米诺骨牌需要推倒第一张。缺少奠基步骤，整个归纳链条无从开始。例如证明 $n=n+1$时，若错误地假设$k=k+1$成立，则$k+1=(k+1)+1$，看似"推出"了——但奠基永远不成立，这正是谬误所在。
错误3：归纳步骤中的逻辑漏洞
- 从 $P(k)$推出$P(k+1)$的推理必须对所有$k \geq n_0$有效，不能只对特定的$k$ 成立；
- 不等式归纳中，放缩要确保方向一致，乘除负数时不等号方向需反转；
- 第二归纳法中，有时只需部分假设（如仅有 $P(k)$和$P(k-1)$），但声明时需明确。
错误4：归纳变量混淆
如果命题涉及多个变量，必须明确对哪个变量进行归纳。例如证明 $\binom{n}{k}$的恒等式，通常对$n$归纳，此时$k$ 视为参数。
归纳法的灵活运用
- 若直接归纳困难，尝试加强命题（归纳假设更强）；
- 若递推跨越多个步长，考虑跳跃归纳或第二归纳法；
- 若涉及自然数分组（奇偶、模 $d$ 同余），可分别归纳；
- 证明过程中，归纳假设的"形式"比"内容"更重要——把 $P(k)$ 精确地写出来再代入。