2.1 数学归纳法

动机

许多数学命题包含无限多个情形。例如

$$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}2\right)^2$$

对每个正整数 $n$ 都提出断言。有限检验可以发现规律，却不能证明全部情形； 归纳法先验证起点，再证明真值沿所需过渡传递。

命题、起点与合法的递推步骤

定义

索引命题与普通归纳法的数据

索引命题 $P(n)$ 对声明范围内每个整数 $n$ 都有确定真值。在 $n\ge n_0$ 上进行普通归纳证明时，需要：

1. 基础情形 $P(n_0)$；
2. 对任意 $k\ge n_0$ 作出的归纳假设 $P(k)$；
3. 归纳步骤 $P(k)\Rightarrow P(k+1)$。

归纳假设只可在归纳步骤内使用；最后仍须引用归纳法原理才得到全称结论。

定义

步长、连续基础情形与强归纳假设

对于 $d\in\mathbb Z^+$，步长为 $d$ 的归纳法证明 $P(k)\Rightarrow P(k+d)$。它只能到达与起点 同属一个剩余类的指标，所以声称覆盖的每个剩余类都必须有基础情形。 连续基础情形归纳法先验证若干相邻情形，再使用相应假设，例如 $P(k),P(k+1)\Rightarrow P(k+2)$。强归纳法证明 $P(k+1)$ 时可使用 $P(n_0),\ldots,P(k)$。

定义

前向与后向归纳法

此方法从 $P(1)$ 出发，并使用两个蕴涵：

$$P(k)\Rightarrow P(2k)\quad(k\ge1), \qquad P(k)\Rightarrow P(k-1)\quad(k\ge2).$$

倍增步骤到达二的幂；后退步骤填补其下的空缺。

对于存在性命题，$P(n)$ 必须保留存在量词。例如在硬币问题中，命题不能只写 $n=3a+5b$，而应写成“存在 $a,b\in\mathbb Z_{\ge0}$，使得 $n=3a+5b$”。对于涉及任意实数输入的命题，$P(n)$ 还必须量化这些输入，并 保留全部定义域条件。

归纳法为何能覆盖每个所需指标

定理

从任意起点开始的普通归纳法

设 $n_0\in\mathbb Z$，并且命题 $P(n)$ 对每个整数 $n\ge n_0$ 都有定义。 如果 $P(n_0)$ 成立，而且对每个整数 $k\ge n_0$ 都有 $P(k)\Rightarrow P(k+1)$，那么 $P(n)$ 对每个 $n\ge n_0$ 都成立。

定理

步长归纳法与连续基础情形归纳法

设 $d\in\mathbb Z^+$、$n_0\in\mathbb Z$，且 $P(n)$ 对每个整数 $n\ge n_0$ 有定义。若 $P(n_0),\ldots,P(n_0+d-1)$ 成立，而且对每个整数 $k\ge n_0$ 都有 $P(k)\Rightarrow P(k+d)$，则 $P(n)$ 对每个 $n\ge n_0$ 成立。更一般地， 若 $P(1),\ldots,P(d)$ 成立，而且对每个整数 $k\ge1$，$d$ 个命题 $P(k),\ldots,P(k+d-1)$ 共同推出 $P(k+d)$，则 $P(n)$ 对每个正整数 $n$ 成立。

定理

强归纳法

设 $n_0\in\mathbb Z$，且命题 $P(n)$ 对每个整数 $n\ge n_0$ 有定义。假设 $P(n_0)$ 成立，并且对每个整数 $k\ge n_0$，联合假设 $P(n_0),P(n_0+1),\ldots,P(k)$ 都能推出 $P(k+1)$，那么 $P(n)$ 对每个 $n\ge n_0$ 都成立。

定理

前向与后向归纳法

设命题 $P(n)$ 对 $n\in\mathbb Z^+$ 有定义。若 $P(1)$ 成立，且对 $k\ge1$ 有 $P(k)\Rightarrow P(2k)$，对 $k\ge2$ 有 $P(k)\Rightarrow P(k-1)$，那么 $P(n)$ 对每个正整数 $n$ 都成立。

可达性与最小反例论证

普通归纳法可以用最小反例原理说明。假如某个满足 $n\ge n_0$ 的 $P(n)$ 不 成立，取最小反例的指标 $m$。基础情形给出 $m\ne n_0$，因此 $m-1\ge n_0$。由于 $m$ 最小，$P(m-1)$ 成立；归纳步骤随即推出 $P(m)$ 成立，产生矛盾。强归纳法的逻辑相同：最小性恰好提供了较强假设所需的每个较早 情形。

对于步长 $d$，应把指标画成 $d$ 条独立的链。从 $r$ 出发，蕴涵只能到达 $r+d,r+2d,\ldots$，不会到达其他剩余类。对于二阶递推关系，两个基础情形 会启动一个滑动窗口：$P(1),P(2)$ 先给出 $P(3)$，再由 $P(2),P(3)$ 按照 声明的顺序给出 $P(4)$。

前向与后向归纳法需要证明可达性。给定目标 $n$，选择满足 $2^r\ge n$ 的 $r\in\mathbb Z_{\ge0}$。反复加倍得到 $P(1),P(2),P(4),\ldots,P(2^r)$，再反复减一得到 $P(2^r-1),\ldots,P(n)$。每个向后步骤都是从至少为 $2$ 的指标开始，因而 没有越过其假设范围。

按递推结构选择归纳假设

证明: 立方和证明的依赖关系

目标与基础情形。 对 $n\in\mathbb Z^+$，令 $P(n)$ 为 $\sum_{r=1}^n r^3=n^2(n+1)^2/4$。$n=1$ 时两边均为 $1$。

假设与目标。 固定任意整数 $k\ge1$，假设 $P(k)$；须证 $P(k+1)$，不能只改写 $P(k)$。

合法步骤与依赖。 分离末项，仅对前 $k$ 项使用假设，再因式分解：

$$\sum_{r=1}^{k+1}r^3 =\underbrace{\sum_{r=1}^{k}r^3}_{\text{使用 }P(k)}+(k+1)^3 =\frac{(k+1)^2}{4}\bigl(k^2+4(k+1)\bigr) =\frac{(k+1)^2(k+2)^2}{4}.$$

边界与收束。 拆分对所有 $k\ge1$ 合法，包括首步 $1\to2$。末式正是目标；结合基础情形，普通归纳法给出全部 $P(n)$。

例题

1. 普通归纳法：整除命题

令 $P(n)$ 表示 $3\mid(n^3-n)$（$n\in\mathbb Z^+$）。基础情形为 $1^3-1=0=3\cdot0$。对任意整数 $k\ge1$，假设 $k^3-k=3q$，其中 $q\in\mathbb Z$。于是

$$(k+1)^3-(k+1)=3(q+k^2+k),$$

所以下一个值仍可被 $3$ 整除。再次应用归纳法即可得到对每个正整数 $n$ 的结论； 整数 $q$ 使整除假设准确无歧义。

例题

2. 带定义域条件的三角函数裂项相消恒等式

对每个 $n\ge1$，令 $P(n)$ 表示：对于每个满足 $\sin(jx)\ne0$（$j=1,\ldots,n+1$）的实数 $x$，都有

$$\sum_{r=1}^{n}\frac1{\sin(rx)\sin((r+1)x)} =\frac{\sin(nx)}{\sin^2x\sin((n+1)x)}.$$

$n=1$ 时可以约分；该运算成立是因为 $\sin x\ne0$。进行归纳步骤时，满足 $k+1$ 情形定义域条件的 $x$ 也满足 $k$ 情形。加入新的一项，并使用

$$\sin(kx)\sin((k+2)x)+\sin^2x=\sin^2((k+1)x).$$

根据已经声明的非零条件约分后，结果为 $\sin((k+1)x)/(\sin^2x\sin((k+2)x))$。因此公式本身和证明中的每次除法 都得到了说明。

例题

3. 从任意指标开始

令 $P(n)$ 为 $n^2\lt2^n$，其中 $n\ge5$。基础情形是 $25\lt32$。若 $k^2\lt2^k$ 且 $k\ge5$，则 $2k+1\lt k^2$，所以

$$(k+1)^2=k^2+2k+1\lt2k^2\lt2^{k+1}.$$

证明从 $5$ 开始，是因为上述估计与原命题都只需要从该指标起成立。

反例模式

重述假设不能证明下一情形

假命题 $Q(n):n^2\lt2^n$ 声称对所有正整数成立。$Q(1)$ 真，因为 $1\lt2$； $Q(2)$ 假，因为 $4=4$；$n=3,4$ 也失败，分别有 $9\gt8$、$16=16$。然而 $Q(k)\Rightarrow Q(k)$ 对每个 $k$ 都真，只是重述假设。 故真起点加这个蕴涵不能代替归纳步骤；有限验算也不提供过渡。

修复是前例的 $n\ge5$ 命题：验证 $25\lt32$，再用 $2k+1\lt k^2$ 证明 每个整数 $k\ge5$ 的 $Q(k)\Rightarrow Q(k+1)$。定义域与下一情形都不可省略。

例题

4. 二阶线性递推关系所需的两个连续基础情形

令 $\alpha=3+\sqrt5$、$\beta=3-\sqrt5$，并定义 $a_n=\alpha^n+\beta^n$。由于 $\alpha+\beta=6$ 且 $\alpha\beta=4$，可得

$$a_{n+2}=6a_{n+1}-4a_n.$$

现在 $a_1=6$，$a_2=28$。若对某些整数 $M,N$ 有 $a_k=2^kM$ 及 $a_{k+1}=2^{k+1}N$，那么

$$a_{k+2}=2^{k+2}(3N-M).$$

因此，对所有 $n\ge1$ 都有 $2^n\mid a_n$。由于递推关系使用前面两项， 两个基础情形缺一不可。

例题

5. 硬币问题中的三个剩余类

对 $t\in\mathbb Z_{\ge8}$，令 $P(t)$ 表示：存在 $a,b\in\mathbb Z_{\ge0}$，使得 $t=3a+5b$。 三个基础情形

$$8=3+5,\qquad9=3+3+3,\qquad10=5+5$$

覆盖模 $3$ 的全部剩余类。若 $P(t)$ 成立，加入一枚 $3$ 分硬币便证明 $P(t+3)$。从 $8,9,10$ 开始的三条链共同覆盖每个整数 $t\ge8$；只验证基础情形 并不足够。

例题

6. 强归纳法：素数乘积与相异二的幂之和

对于素数乘积，令 $P(n)$ 只断言 $n\ge2$ 时分解的存在性。基础情形 $2$ 本身是素数。若从 $2$ 到 $k$ 的所有整数都有这种分解，则 $k+1$ 或者是素数， 或者 $k+1=ab$，其中 $2\le a,b\le k$；在后一种情况下，用强归纳假设分别 分解 $a$ 和 $b$。这个论证证明存在性，并不证明唯一性。

令 $P(n)$ 表示 $n$ 可写成互不相同的二的非负整数次幂之和。基础情形 $P(1)$ 由 $1=2^0$ 给出。假设 $P(1),\ldots,P(k)$，选择不超过 $k+1$ 的最大项 $2^\ell$（$\ell\in\mathbb Z_{\ge0}$），并令 $m=k+1-2^\ell$。若 $m=0$， 单项表示已经完成。若 $m\ge1$，则 $m\le k$，强归纳假设可以表示 $m$；而且 $m\lt2^\ell$，故表示中没有任何二的幂等于 $2^\ell$。加入 $2^\ell$ 后，各项仍互不相同。必须把 $m=0$ 单独处理，因为 我们从未假设 $P(0)$。

例题

7. 巧克力板究竟需要折断多少次

设 $n,m\in\mathbb Z^+$。假定每次折断只能选取一块已有的长方形，不能叠放，也不能同时切割多块，并沿着 网格线把它分成两块。从一块开始，每次折断都恰好使块数增加一，所以要得到 $nm$ 个单位正方形，至少需要 $nm-1$ 次折断。这个下界能够达到：先横向折 $n-1$ 次，得到 $n$ 行，再在每一行内折 $m-1$ 次。总次数为

$$(n-1)+n(m-1)=nm-1.$$

也可以对 $n+m$ 归纳：先把巧克力板分成两个较小的长方形，再对它们应用结论。 块数不变量证明必要性，明确的折断构造证明充分性。

例题

8. 用前向与后向归纳法证明均值平方不等式

令 $P(n)$ 为以下全称命题：每个由正实数组成的 $n$ 元组都满足

$$\left(\frac{x_1+\cdots+x_n}{n}\right)^2 \le\frac{x_1^2+\cdots+x_n^2}{n}.$$

$P(1)$ 为等式。当 $k\ge1$ 时，为了由 $P(k)$ 得到 $P(2k)$，把 $2k$ 个数分成两组，对 两组的平均数使用 $((u+v)/2)^2\le(u^2+v^2)/2$，再分别对每组使用 $P(k)$。当 $k\ge2$ 时，为了由 $P(k)$ 得到 $P(k-1)$，在 $x_1,\ldots,x_{k-1}$ 后面添上它们的平均数 $\mu$。对这 $k$ 个数应用 $P(k)$，得到

$$\mu^2\le\frac{\sum_{i=1}^{k-1}x_i^2+\mu^2}{k}, \qquad (k-1)\mu^2\le\sum_{i=1}^{k-1}x_i^2.$$

把末式除以 $k-1>0$，得到 $\mu^2\le\sum_{i=1}^{k-1}x_i^2/(k-1)$，这才是 $P(k-1)$。结合可达性论证即可证明每个 $P(n)$。若 $\mu$ 是 $x_1,\ldots,x_n$ 的平均数，则

$$\frac1n\sum_{i=1}^n x_i^2-\mu^2 =\frac1n\sum_{i=1}^n(x_i-\mu)^2,$$

所以等号成立当且仅当 $x_1=\cdots=x_n$。

常见错误

常见错误

错误的马匹证明在第一步失去交集

错误证明比较集合 $\{h_1,\ldots,h_n\}$ 与 $\{h_2,\ldots,h_{n+1}\}$。 两组只有在 $n\ge2$ 时才相交；关键过渡 $P(1)\Rightarrow P(2)$ 中没有共同的马， 故基础情形虽真，归纳链仍未启动。

常见错误

归纳步骤未必能到达每个声称的指标

由 $P(1)$ 出发且每次使用 $k\mapsto k+2$，只能证明奇数指标。二阶递推也不能 只靠一个基础情形启动。下结论前应列出实际可达指标。

常见错误

定义域条件与量词都属于 P(n)

没有排除正弦的零点便进行约分、在强归纳假设从 $1$ 开始时把它应用于 $0$， 或者在命题声称“每个元组”时只证明一个方便的元组，都会改变原命题。归纳开始 之前必须声明这些限制。

思考检查

问题 1：某证明已知 P(2)，且 P(k) 推出 P(k+2)。它证明了哪些正整数指标？

应追踪实际可达的剩余类，而不要只根据符号猜测。

思考检查

问题 2：在互不相同的二的幂的证明中，为什么必须把余数 m=0 单独处理？

比较强归纳假设的适用范围与余数的值。

总结

归纳法用已验证的起点和覆盖全部目标的过渡证明无限多个命题。普通归纳法前进 一步；任意起点法从首个声称成立的指标开始；步长法覆盖相关剩余类；连续基础 情形配合依赖多个前项的递推；强归纳法可用全部较早情形；前向与后向法先倍增 至足够大的二的幂，再下降到目标。

可靠流程是：写出带量词和定义域的 $P(n)$，写明起点，验证所有基础情形，选取范围内任意 $k$， 只用可用假设证明目标，检查可达性，再引用相应定理。零余数、零分母或缺失的 首次过渡，都是证明的一部分。

练习

1. 对 $n\in\mathbb Z^+$，用归纳法证明下列命题；其中（e）证明更强的 $n\in\mathbb Z_{\ge0}$ 情形。在（e）和（f）中先证明对每个实数角都成立 的交叉相乘恒等式，再声明商式的分母非零条件。

   （a）$\displaystyle\sum_{r=1}^n r(r+1)(r+2)=\frac14n(n+1)(n+2)(n+3)$。

   （b）$\displaystyle\sum_{r=1}^n\frac1{(2r-1)(2r+1)}=\frac{n}{2n+1}$。

   （c）$5\mid(3^{2n}-2^{2n})$。

   （d）$64\mid(9^n-8n-1)$。

   （e）$\displaystyle 2^{n+1}\sin\theta\prod_{r=0}^n\cos(2^r\theta) =\sin(2^{n+1}\theta)$。

   （f）$\displaystyle \sin\frac{x}{2}\sum_{r=1}^n\sin(rx) =\sin\frac{(n+1)x}{2}\sin\frac{nx}{2}$。

   因此，当 $\sin\theta\ne0$ 时，可以把（e）除以 $2^{n+1}\sin\theta$，得到相应的正弦商式；当 $\sin(x/2)\ne0$ 时，也可 把（f）除以 $\sin(x/2)$，得到相应商式。

2. 直角三格骨牌是由三个共边单位方格组成的 L 形骨牌。证明：对于每个 $n\in\mathbb Z^+$，从一块 $2^n\times2^n$ 棋盘中任意移去一个方格后，剩余部分都能 用这种骨牌铺满。

3. 用步长为 $2$ 的归纳法证明：（a）对每个正偶数 $n$，都有 $23\mid(12^n-11^n)$；（b）对每个正奇数 $n$，都有 $11\mid(7^n+4^n)$。

4. 设 $x\in\mathbb R\setminus\{0\}$，并假设 $s=x+x^{-1}$ 为整数。证明对 每个 $n\in\mathbb Z_{\ge0}$，$x^n+x^{-n}$ 都是整数。

5. 证明每个不少于 $12$ 分的邮资都能用 $4$ 分与 $5$ 分邮票组成。

6. 设 $F_0=0$、$F_1=1$ 且 $F_{n+2}=F_{n+1}+F_n$（$n\ge0$）。证明每个自然数本身 是一个斐波那契数，或者可以写成互不相同的正斐波那契数之和；重复值 $F_1=F_2=1$ 只计一次。只需证明存在性。

7. 对同一个斐波那契数列证明：（a）当 $n\ge0$ 时， $\sum_{i=0}^nF_i^2=F_nF_{n+1}$；（b）当 $m,n\ge0$ 时， $F_nF_m+F_{n+1}F_{m+1}=F_{n+m+1}$；（c）若 $\phi\gt\psi$ 是 $t^2-t-1=0$ 的两个根，则对 $n\ge0$ 有 $F_n=(\phi^n-\psi^n)/\sqrt5$。

8. 对 $m,n\in\mathbb Z^+$ 及非负实数 $x_1,\ldots,x_n$，证明

$$\left(\frac{x_1+\cdots+x_n}{n}\right)^m \le\frac{x_1^m+\cdots+x_n^m}{n}.$$

答案与解答

解答 · 快速检查问题 1

只能到达正偶数指标 $2,4,6,\ldots$。如果还要证明奇数指标，就需要在奇数 剩余类中另设一个基础情形。

解答 · 快速检查问题 2

强归纳假设只覆盖 $P(1),\ldots,P(k)$，并不包括 $P(0)$。当 $m=0$ 时，应直接 使用单项表示 $k+1=2^\ell$。

解答 · 第 1 题解答

（a）$n=1$ 时两边均为 $6$。在归纳假设的等式两边加上 $(k+1)(k+2)(k+3)$，再分解为 $\tfrac14(k+1)(k+2)(k+3)(k+4)$。（b）基础情形是 $1/3=1/3$。若前 $k$ 项之和为 $k/(2k+1)$，加入下一项便得 $k/(2k+1)+1/((2k+1)(2k+3))=(k+1)/(2k+3)$。裂项公式 $1/((2r-1)(2r+1))=\tfrac12(1/(2r-1)-1/(2r+1))$ 也给出相同的端点公式。 把前两项相加，可以直接核对端点。

（c）基础情形为 $9-4=5$，并且 $3^{2(k+1)}-2^{2(k+1)}=9(3^{2k}-2^{2k})+5\cdot2^{2k}$。 （d）基础情形 $n=1$ 的表达式为 $9-8-1=0$；用第 $k+1$ 个表达式减去第 $k$ 个表达式， 得到 $9^{k+1}-8(k+1)-1-(9^k-8k-1)=8(9^k-1)$。由于 $9^k-1$ 可被 $8$ 整除，该差可被 $64$ 整除。

（e）证明更强的 $n\ge0$ 情形；基础是 $2\sin\theta\cos\theta=\sin2\theta$。把第 $k$ 个 恒等式乘以 $2\cos(2^{k+1}\theta)$。商式还要求 $\sin\theta\ne0$。 （f）$n=1$ 时两边均为 $\sin(x/2)\sin x$。使用归纳假设并加入 $\sin((k+1)x)$ 后，应用

$$\sin\frac{(k+1)x}{2} \left(\sin\frac{(k+2)x}{2}-\sin\frac{kx}{2}\right) =\sin\frac{x}{2}\sin((k+1)x).$$

商式还要求 $\sin(x/2)\ne0$。

解答 · 第 2 题解答

$n=1$ 时，$2\times2$ 棋盘中剩下的三个方格恰好组成一块直角三格骨牌。把 $2^{k+1}\times2^{k+1}$ 棋盘分成四个 $2^k\times2^k$ 象限。其中一个 象限包含被移去的方格。在中央放置一块三格骨牌，覆盖另外三个象限各自最靠近 中心的方格。这样每个象限都恰好缺少一个方格，归纳假设便能铺满全部四个象限。

解答 · 第 3 题解答

（a）从 $n=2$ 开始，且 $12^2-11^2=23$。若命题对偶数 $k$ 成立，则 $12^{k+2}-11^{k+2}=121(12^k-11^k)+23\cdot12^k$，故它对 $k+2$ 也 成立。（b）从 $n=1$ 开始，且 $7+4=11$。若命题对奇数 $k$ 成立，则 $7^{k+2}+4^{k+2}=16(7^k+4^k)+33\cdot7^k$，故它对 $k+2$ 也成立。

解答 · 第 4 题解答

令 $a_n=x^n+x^{-n}$。则 $a_0=2$、$a_1=s$，直接相乘得到 $a_{n+2}=sa_{n+1}-a_n$。用两个连续基础情形进行归纳，便可证明对所有 $n\ge0$ 都有 $a_n\in\mathbb Z$。

解答 · 第 5 题解答

使用四个基础情形 $12=3\cdot4$、$13=2\cdot4+5$、$14=4+2\cdot5$ 及 $15=3\cdot5$。 若金额 $t$ 可以组成，再加一枚 $4$ 分邮票就能组成 $t+4$。这四条剩余类链 覆盖每个不少于 $12$ 的整数。

解答 · 第 6 题解答

$0=F_0$ 的情形立即成立。对于 $n\gt0$，使用强归纳法。选择不超过 $n$ 的 最大斐波那契数值 $F_j$。若 $n=F_j$，证明完成；否则令 $r=n-F_j$。由于 $n\lt F_{j+1}=F_j+F_{j-1}$，有 $0\lt r\lt F_{j-1}$。根据归纳假设， $r$ 是一个斐波那契数值或者若干互不相同的斐波那契数值之和，而且这些数值都 小于 $F_{j-1}$；加入 $F_j$ 后各加数仍互不相同。这只证明存在性，并未断言 表示唯一。

解答 · 第 7 题解答

（a）$n=0$ 的基础情形立即成立。加入 $F_{k+1}^2$ 后得到 $F_kF_{k+1}+F_{k+1}^2=F_{k+1}F_{k+2}$。

（b）固定 $n$。$m=0$ 时两边均为 $F_{n+1}$，$m=1$ 时均为 $F_{n+2}$。 若公式对 $m$ 和 $m+1$ 成立，把两个左端相加就得到 $m+2$ 情形的左端；而 $F_{n+m+1}+F_{n+m+2}=F_{n+m+3}$。

（c）每个根 $u$ 都满足 $u^{k+2}=u^{k+1}+u^k$，所以所给公式满足斐波那契 递推关系。又因为 $\phi-\psi=\sqrt5$，它在 $n=0,1$ 时的值为 $0,1$。 两个连续基础情形完成证明。

解答 · 第 8 题解答

先对 $m$ 归纳，证明当 $u,v\ge0$ 时 $(u+v)^m\le2^{m-1}(u^m+v^m)$；$m=1$ 时为等式。假设上述不等式对某个 $m\in\mathbb Z^+$ 成立， 两边乘以 $u+v$，再使用 $u^mv+uv^m\le u^{m+1}+v^{m+1}$；这等价于 $(u-v)(u^m-v^m)\ge0$。所以

$$(u+v)^{m+1} \le2^{m-1}(u^m+v^m)(u+v) \le2^m(u^{m+1}+v^{m+1}).$$

归纳法证明上述不等式对每个 $m\in\mathbb Z^+$ 成立。由于 $m$ 是任意正整数， 将上述不等式两边除以 $2^m$，得到

$$\left(\frac{u+v}{2}\right)^m\le\frac{u^m+v^m}{2}.$$

现在重复例题 8 的前向与后向论证：加倍时把 $2k$ 个输入分成两组，每组 $k$ 个；向后时添上前 $k-1$ 个输入的平均数。选择 $2^r\ge n$，从 $1$ 不断加倍至 $2^r$，再逐次减一到 $n$。当 $n=1$ 或 $m=1$ 时必取等号。 当 $n\ge2$ 且 $m\ge2$ 时，由严格凸性或二元步骤的等号条件可知，等号成立当且仅当所有 $x_i$ 相等。