高中数学/不等式与数列/数学归纳法

阅读指南

希望快速了解或快速回顾高中数学的读者可以只看基础知识部分。其余部分是为需要参加学科考试或需要一定知识提升的读者准备的。

本节介绍的数学归纳法在数学的各个领域中都有重要作用，是一种通用性比较广的代数证明方法，主要适用于证明对于正整数恒成立的相关命题。集合论中适用于超限数的超限归纳法是数学归纳法的重要推广。作为定义自然数的主要（不是唯一的）公理化方式的皮亚诺公理也蕴含数学归纳法的思想。数学归纳法也会在学习极限时发挥很大作用。

预备知识

本节内容涉及函数迭代与数列递推的概念，所以读者应该先阅读复合函数与一阶递推数列章节。

考试要求

在中国大陆高考中，数学归纳法曾是理科数学试卷的考查点之一，常用于解决大题中的结论证明，一般出题难度中等，是比较常用的代数证明方法。而对于高考取消文理分科考法的地区，目前并不将其纳入必考知识范围，只将其列为选学内容。不过由于数学归纳法简单易学，并且是非常重要的代数证明方法，我们仍将其纳入主干知识的范围。

基础知识

知识引入

假设一个数列$\{a_n\}$的通项公式是$a_n=(n^2-5n+5{)}^2$，容易验证此数列前4项的取值都是1，但是我们不能就此认为它的第5项也等于1。实际上容易验证$a_5=25\ne 1$。这说明看上去可能成立的规律并非总是可靠。

再比如已知$a+b+c=1,a^2+b^2+c^2=2,a^3+b^3+c^3=3$，要求$a^4+b^4+c^4$的值。由于前3个式子的计算结果依次为1、2、3，首先最容易猜想第4个式子的结果有可能是4，但是再稍微想一想就会发现支持答案为4的理由并不明显。事实上，这是一道需要使用多个多元等幂和公式求解的坑人题，而且其答案确实不是一开始最容易想到的4。如果继续增加变量和已知算式的个数，这个题还可以变得更为迷惑人。总而言之，基于有限个特例得到的经验并非总是可靠无误。

又比如对于数列$\{b_n\}$，已知$b_1=1,b_{n+1}=\frac{b_n}{1+b_n}(n=1,2,3,\mathrm{...})$。通过对其前4项的计算，容易猜想其通项公式为$b_n=\frac{1}{n}$。可以发现，这种与正整数n有关的命题，包含了无穷多种具体情况，如果逐一通过计算验证显然是不可能做到的。为此需要另想办法，做到只通过有限多个步骤，证明n取所有正整数时命题都成立。而本节介绍的数学归纳法就是通过构建恒成立的递推关系式来达到这个目的。当然对于这种特殊的分式线性递推关系式，在后面的不动点法章节中还会继续介绍其它求解方法。

普通数学归纳法的概念

证明一个与正整数n有关的命题，可以按下列步骤进行：

1. 归纳奠基（base case）：证明当n取第一个值$n_0(n_0\in {ℝ}^{+})$时命题成立；
2. 归纳递推（induction step）：假设$n=k(k>n_0,k\in {ℝ}^{+})$时命题成立，继续证明当$n=k+1$时命题也成立。

只要完成这2个步骤，就可以断定命题对于从$n_0$开始的所有正整数n都成立。
这个证明方法叫做数学归纳法（mathematical induction），简称“数归法”（MI）。

数学归纳法可以用流程框图表示为（在维基教科书输入中文流程图不方面，先将就着看吧……）：
$\begin{array}{c}\text{prove that the proposition holds for n = }{n}_0\\ \text{given the proposition holds for n = k}(k\ge n_0),\text{ prove it still holds when }n=k+1\end{array}\}\Rightarrow \text{the proposition holds for all n }(n\ge n_0)$
$\begin{array}{c}\text{归 纳 奠 基 ：简 单 验 证 }n=n_0\text{时 命 题 成 立}\\ \text{归 纳 递 推 ：假 设 }n=k(k\ge n_0)\text{时 命 题 成 立 ，证 明 n = k+1时 命 题 也 成 立}\end{array}\}\Rightarrow \text{命 题 对 从 }{n}_0\text{开 始 的 所 有 正 整 数 n都 成 立 }$

相关例题： 已知在数列$\{b_n\}$中，有$b_1=1,b_n=\frac{b_n}{b_n+1}(n\ge 1,n\in {\mathbb{N}}^{+})$，使用数学归纳法证明：$b_n=\frac{1}{n}$。

数学归纳法的论证思路借助了多米诺骨牌效应。

一个与数学归纳法密切相关的生活实例是多米诺骨牌游戏。可以看出，只要满足以下2个条件，所有多米诺骨牌就都能倒下：

1. 保证第1个块骨牌倒下；
2. 对于任意两块相邻的骨牌，保证前一块倒下时一定导致后一块也倒下。

其递推关系为：当第k块倒下时，与其相邻的第k+1块也一定倒下。此时，只需要设法推倒第一块骨牌，即可保证其它骨牌一定都会倒下。

数学归纳法是一种环环相扣的无限递推的论证方法，其思路就像多米诺骨牌游戏一样，可以使一连串的无穷个命题依次地得到证明。其中每一环的论证都依赖于前一环的成功论证以及相邻命题之间递推关系的成立。这个证明过程中最重要的一步就是找到并证明相邻命题之间递推关系，也就是要将一个较大的问题设法化归为（或者说递归地表达为）一个规模更小、更易解决的问题。

提示：某些版本的高中数学教材上还有介绍“不完全归纳法”与“完全归纳法”的概念，并指出数学归纳法是一种完全归纳法。由于这方面的介绍和讨论只是枯燥的逻辑学问题，而不是数学问题，故我们学习数学时其实没有必要了解什么是不完全归纳法。

证明等式

相关例题1： 使用数学归纳法求证：$(x+1{)}^n=(x+1)+x(x+1)+x(x+1{)}^2+\cdots +x(x+1{)}^{n-1}$。

相关例题2： 使用数学归纳法求证下列等幂求和公式：
(1) $1+2+3+\cdots +n=\frac{n(1+n)}{2}$。
(2) $1^2+2^2+3^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$。
(3) $1^3+2^3+3^3+\cdots +n^3=(\frac{n(n+1)}{2}{)}^2$。

相关例题3： 求证：$1\times 4+2\times 7+3\times 10+\mathrm{...}+n(3n+1)=n(n+1{)}^3(n\in {\mathbb{N}}^{+})$。

相关例题4： 求证：$1^2-2^2+3^2-4^2+\mathrm{...}+(2n-1{)}^2-(2n{)}^2=-n(2n+1)(n\in {\mathbb{N}}^{+})$。

相关例题5： 求证：$-1+3-5+\mathrm{...}+(-1{)}^n(2n-1)=(-1{)}^{n}n$。

相关例题6： 求证：$1\times n+2\times (n-1)+3\times (n-2)+\mathrm{...}+n\times 1=\frac{n(n+1)(n+2)}{6}$。

相关例题7： Find and prove by induction a formula for $\sum _{i=1}^n(2i-1)$ (i.e., the sum of the first n odd numbers), where $n\in {\mathbb{Z}}_{+}$.

相关例题8： 利用数学归纳法求证：
$(1\cdot 2^2-2\cdot 3^2)+(3\cdot 4^2-4\cdot 5^2)+\mathrm{...}+((2n-1)\cdot (2n{)}^2-2n\cdot (2n+1{)}^2)=-n(n+1)(4n+3)$

相关例题9： Let $x\ne 0$ be a real number such that $x+x^{-1}\in \mathbb{Z}$. Prove that for any $n\in \mathbb{Z},x^n+x^{-n}\in \mathbb{Z}$.

相关例题10： Find and prove by induction a formula for $\prod _{i=2}^n(1-\frac{1}{i^2})$, where $n\in {\mathbb{Z}}_{+}$ and $n\ge 2$.

相关例题11： Prove that $\sum _{i=1}^{n}i\cdot (i!)=(n+1)!-1$.

相关例题12： Prove that $\prod _{i=1}^n\frac{i^2}{i+1}=\frac{n!}{n+1}$.

相关例题13： 求证韦达定理对n次实系数方程成立。（如果不知道代数基本定理，可以只考虑有n个实数根的n次方程的情况。）

相关例题14： 设正数$w_1$为数字a的权重值，正数$w_2$为数字b的权重值，若定义2个数a和b的加权平均数为$\frac{w_{1}a+w_{2}b}{w_1+w_2}$，求证n个数的加权平均数计算公式为：
$\frac{w_1{x}_1+w_2{x}_2+\mathrm{...}+w_n{x}_n}{w_1+w_2+\mathrm{...}+w_n}$
其中各个正数$w_i$分别是下标对应的数字$x_i$的权重值。

相关例题15： 使用数学归纳法证明等幂和公式：
$a^n-b^n=(a-b)\sum _{r=1}^n{a}^{n-r}{b}^{r-1}=(a-b)(a^{n-1}+a^{n-2}b+\mathrm{...}+b^{n-1})$

相关例题16： Number of subsets: Show that a set of n elements has $2^n$ subsets.

相关例题17： Number of 2-element subsets: Show that a set of n elements has $\frac{n(n-1)}{2}$ subsets with 2 elements. (Take n = 2 as the base case.)

相关例题18： Generalization of De Morgan's Law to unions of n sets. Show that if $A_1,A_2,\mathrm{...},A_n$ are sets, then
$\overline{A_1\cup \mathrm{...}\cup A_n}=\overline{A_1}\cap \mathrm{...}\cap \overline{A_n}$.

常用结论与常见模型

简单的整除性问题

相关例题1： 求证：形如$n^3+5n(n\in {\mathbb{N}}^{+})$的数总能够被6整除。

相关例题2： 求证：形如$8^n-3^n(n\in {\mathbb{N}}^{+})$的数总能够被5整除。

相关例题3： Use the Principle of Mathematical Induction to verify that, for n any positive integer, $6^n-1$ is divisible by 5.

参数求值问题

相关例题1： 求使得关系式$1\times 2+4\times 3+9\times 4+\cdots +n^2(n+1)=\frac{n}{m}(n+1)(n+2)(3n+1)$恒成立的m的取值。

相关例题2： 如果对于任意的$n\in {\mathbb{N}}^{+}$，$3^{4n+2}+a^{2n+1}$都能被14整除，求a可以取的最小自然数。

抽象推理

相关例题1： 已知函数$f(x)$满足$f(xy)=f(x)+f(y)$，利用数学归纳法证明$f(x^n)=nf(x)(n\in {\mathbb{N}}^{+})$。

证明：
①令y = 1，则有$f(x)=f(x)+f(1)$，即$f(1)=0$。即在此情况下，结论成立。
②假设n = k时，有$f(x^k)=kf(x)$。则当n = k+1时，有：
$f(x^{k+1})=f(x^k\ast x)=f(x^k)+f(x)=kf(x)+f(x)=(k+1)f(x)$
所以当n = k+1时，结论也成立。
综合①、②可知，原结论成立。

相关例题2： 设$f(n)=1+\frac{1}{2}+\frac{1}{3}+\mathrm{...}+\frac{1}{n}$，是否存在$g(n)$使得等式$f(1)+f(2)+\mathrm{...}+f(n-1)=g(n)f(n)-g(n)$对满足$n\ge 2$的一切自然数n成立？使用数学归纳法证明这个结论。

几何问题

相关例题1： 求证$n(n\ge 3,n\in \mathbb{N})$边形的内角和公式为$(n-2)\times 180^{\circ }$。

相关例题2： 利用多边形三角剖分（polygon triangulation）思想，求证计算平面$n(n\ge 3,n\in \mathbb{N})$边形面积A的高斯鞋带公式（shoelace formula）： $\begin{array}{cc}𝐀& =\frac{1}{2}|\sum _{i=1}^{n-1}{x}_i{y}_{i+1}+x_n{y}_1-\sum _{i=1}^{n-1}{x}_{i+1}{y}_i-x_1{y}_n|\\ & =\frac{1}{2}|x_1{y}_2+x_2{y}_3+\cdots +x_{n-1}{y}_n+x_n{y}_1-x_2{y}_1-x_3{y}_2-\cdots -x_n{y}_{n-1}-x_1{y}_n|\end{array}$
其中$(x_1,y_1),(x_2,y_2),\mathrm{...},(x_n,y_n)$依次是n边形的各个顶点。

提示：鞋带公式也可以被视为微积分学中格林公式的离散化版本。

相关例题3： 平面多边形X可以被剖分为n个有限的简单图形$X_1,X_2,\mathrm{...},X_n$，这些简单图形的重心坐标依次为$(C_{1x},C_{1y}),(C_{2x},C_{2y}),\mathrm{...},(C_{nx},C_{ny})$，面积依次为$A_1,A_2,\mathrm{...},A_n$。
(1) 根据重心的定义，求证这个平面多边形的整体重心坐标$(C_x,C_y)$可计算如下：
$\{\begin{array}{c}{C}_x=\frac{\sum C_{i_x}{A}_i}{\sum A_i}=\frac{C_{1x}{A}_1+C_{2x}{A}_2+\mathrm{...}+C_{nx}{A}_n}{A_1+A_2+\mathrm{...}+A_n}\\ C_y=\frac{\sum C_{i_y}{A}_i}{\sum A_i}=\frac{C_{1y}{A}_1+C_{2y}{A}_2+\mathrm{...}+C_{ny}{A}_n}{A_1+A_2+\mathrm{...}+A_n}\end{array}$
(2) 若一个正$n(n\ge 3,n\in \mathbb{N})$边形的各个顶点坐标依次为$(x_1,y_1),(x_2,y_2),\mathrm{...},(x_n,y_n)$。利用多边形三角剖分思想和鞋带公式，求证其重心坐标公式为：
$\{\begin{array}{c}{C}_x=\frac{1}{6A}\sum _{i=1}^n(x_i+x_{i+1})(x_i{y}_{i+1}-x_{i+1}{y}_i)\\ C_y=\frac{1}{6A}\sum _{i=1}^n(y_i+y_{i+1})(x_i{y}_{i+1}-x_{i+1}{y}_i)\end{array}$

强数学归纳法

强归纳法（strong induction）也叫完整数学归纳法（complete induction）或第二数学归纳法，是普通数学归纳法的最常用的变体。它仍用于证明与正整数n有关的命题，但其论证步骤变为：

1. 归纳奠基（base case）：证明当n取第一个值$n_0(n_0\in {ℝ}^{+})$时命题成立；
2. 归纳递推（induction step）：假设$n<k(k>n_0,k\in {ℝ}^{+})$时命题成立，继续证明当$n=k$时命题也成立。

只要完成这2个步骤，就可以断定命题对于从$n_0$开始的所有正整数n都成立。

我们知道，使用普通数学归纳法的重点和难点是要将一个较大的问题设法化归为（或者说递归地表达为）一个规模更小、更易解决的问题。但是有时候，将一个较大的问题设法化归为（或者说递归地表达为）有限多个规模更小、更易解决的问题会更容易。这时就要用到强数学归纳法。换句话说，如果一个问题更容易转换为多个小规模的相似子问题解决，而不是只转换为一个小规模的相似子问题解决，则适合考虑使用强数学归纳法。从另一个角度而言，强数学归纳法适合解决涉及二阶和更高阶的递推关系的性质证明。

相关例题1： Consider the famous Fibonacci sequence $\{F_n{\}}_{n=1}^{\mathrm{\infty }}$, defined by the relations $F_1=1,F_2=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\ge 3$. Use an extended Priciple of Mathematical Induction in order to show that for $n\ge 1$, $F_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n)$.
考虑由递推关系$F_1=1,F_2=1,F_n=F_{n-1}+F_{n-2}(n\ge 3)$定义的知名的Fibonacci数列。使用数学归纳法证明它有如下通项公式： $F_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n)$

证明：
①当n = 1时，公式可以验证如下：
$\begin{array}{c}{F}_1=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^1-(\frac{1-\sqrt{5}}{2}{)}^1)\\ =\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2})\\ =\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}-1+\sqrt{5}}{2})\\ =\frac{1}{\sqrt{5}}(\frac{2\sqrt{5}}{2})\\ =1\end{array}$
②当n = 2时，公式可以验证如下：
$\begin{array}{c}{F}_2=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^2-(\frac{1-\sqrt{5}}{2}{)}^2)\\ =\frac{1}{\sqrt{5}}(\frac{1+2\sqrt{5}+5}{4}-\frac{1-2\sqrt{5}+5}{4})\\ =\frac{1}{\sqrt{5}}(\frac{1+2\sqrt{5}+5-1+2\sqrt{5}-5}{4})\\ =\frac{1}{\sqrt{5}}(\frac{4\sqrt{5}}{4})\\ =1\end{array}$
③假设当$n=k,k+1(k\ge 1)$时，公式成立，即$F_k$和$F_{k+1}$此时都符合公式。
此时只需利用递推关系式继续分析$F_{k+2}$：
$\begin{array}{c}{F}_{k+2}=F_{k+1}+F_k\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^{k+1}-(\frac{1-\sqrt{5}}{2}{)}^{k+1})+\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k-(\frac{1-\sqrt{5}}{2}{)}^k)\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^{k+1}+(\frac{1+\sqrt{5}}{2}{)}^k-(\frac{1+\sqrt{5}}{2}{)}^{k+1}-(\frac{1-\sqrt{5}}{2}{)}^k)\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k(\frac{1+\sqrt{5}}{2}+1)-(\frac{1-\sqrt{5}}{2}{)}^k(\frac{1-\sqrt{5}}{2}+1))\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k(\frac{3+\sqrt{5}}{2})-(\frac{1-\sqrt{5}}{2}{)}^k(\frac{3-\sqrt{5}}{2}))\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k(\frac{6+2\sqrt{5}}{4})-(\frac{1-\sqrt{5}}{2}{)}^k(\frac{6-2\sqrt{5}}{4}))\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k(\frac{1+2\sqrt{5}+5}{4})-(\frac{1-\sqrt{5}}{2}{)}^k(\frac{1-2\sqrt{5}+5}{4}))\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^k(\frac{1+\sqrt{5}}{2}{)}^2-(\frac{1-\sqrt{5}}{2}{)}^k(\frac{1-\sqrt{5}}{2}{)}^2)\\ =\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^{k+2}-(\frac{1-\sqrt{5}}{2}{)}^{k+2})\end{array}$
这说明$F_{k+2}$也会满足公式。
综合①、②、③可知，此通项公式对任何的$a_n(n\in {\mathbb{N}}^{+})$都成立。证明完毕。

点评：从Fibonacci数列的通项公式可知：(1)整数数列的通项公式是有可能包含无理系数的；(2)Fibonacci数列与黄金分割比例存在联系。

相关例题2： Prove that $\sum _{i=1}^n{F}_i^2=F_n{F}_{n+1}$ for all $n\in {\mathbb{Z}}_{+}$.

相关例题3： Show that for the Fibonacci numbers, $F_n{F}_{n+2}=F_{n+1}^2+(-1{)}^{n+1}$.

相关例题4： Let the "Tribonacci sequence" be defined by $T_1=T_2=T_3=1$ and $T_n=T_{n-1}+T_{n-2}+T_{n-3}$ for $n\ge 4$. Prove that $T_n<2^n$ for all $n\in {\mathbb{Z}}_{+}$.

相关例题5： Let $a_n$ be the sequence defined by $a_1=1,a_2=8,a_n=a_{n-1}+2a_{n-2}(n\ge 3)$. Prove that $a_n=3\cdot 2^{n-1}+2\cdot (-1{)}^n$ for all $n\in {\mathbb{Z}}_{+}$.

相关例题6： Show that for the Fibonacci numbers,
(1) $gcd(F_{n+1},F_n)=1$;
(2) $gcd(F_m,F_n)=F_{gcd(m,n)}$ for $m,n>0$.

相关例题7： Let $p_0=1,p_1=\cos \theta$ (for $\theta$ some fixed constant) and $p_{n+1}=2p_1{p}_n-p_{n-1}$ for $n\ge 1$. Use an extended Principle of Mathematical Induction to prove that $p_n=\cos (n\theta )$ for $n\ge 0$.

补充习题

• 思考如何将勾股定理推广到$n(n\ge 3,n\in \mathbb{N})$维欧氏空间并给予证明。
• 思考如何利用数学归纳法论证计算格点多边形面积的皮克定理。

外部链接

维基百科中的相关条目：

数学归纳法

维基百科中的相关条目：

递归