2.1 數學歸納法

動機

不少數學命題同時描述無限多個情況。例如恆等式

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

對每個正整數 $n$ 都作出一個斷言。驗算 $n=1,2,3,4$ 可以揭示規律，卻不能 證明餘下的無限多個情況。數學歸納法補上所需的邏輯連接：先確立一個起點，再 證明真確性可沿每一個必要的過渡傳遞下去。

命題、起點與合法的遞推步驟

定義

索引命題與普通歸納法的資料

索引命題 $P(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$，命題 $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$。由最小性知 $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$，選 $r\in\mathbb Z_{\ge0}$ 使 $2^r\ge n$。重複倍增得到 $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)}.$$

在上述 $j=1,2$ 的定義域條件下，$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$。若 $a_k=2^kM$ 且 $a_{k+1}=2^{k+1}N$，其中 $M,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. 強歸納法：質數乘積與相異二的冪之和

對 $n\ge2$，令 $P(n)$ 表示 $n$ 可寫成質數的乘積。$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)$，選最大的 $2^\ell\le k+1$（$\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)$。配合可達性證明便涵蓋所有 $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$，或在全稱命題 中只證明一組方便的輸入，都會改變原命題。這些限制必須在歸納開始前寫明。

思考檢查

Q1. 已知 P(2)，而且 P(k) 推出 P(k+2)，可證明哪些正整數指標？

追蹤可到達的餘數類，不要只看符號猜測。

思考檢查

Q2. 相異二的冪證明中，為何須把餘數 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$）。證明每個自然數本身是 Fibonacci 數，或可寫成互異的正 Fibonacci 數（按數值區分）之和；重複值 $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}.$$

答案與解答

解答 · 快速檢查 Q1

只能到達正偶數指標 $2,4,6,\ldots$。要同時證明奇數指標，須在奇數餘數類另設 基本情況。

解答 · 快速檢查 Q2

強歸納假設只涵蓋至 $k$ 的正整數，並不包括 $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$；相鄰兩式之差是 $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) 加上 $\sin((k+1)x)$ 前，先驗證 $n=1$ 時兩邊均為 $\sin(x/2)\sin 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$ 的最大 Fibonacci 數 $F_j$。若 $n=F_j$ 即完成；否則 $r=n-F_j$ 滿足 $0\lt r\lt F_{j-1}$，因為 $n\lt F_{j+1}=F_j+F_{j-1}$。由歸納假設，$r$ 是 Fibonacci 數或互異的正 Fibonacci 數之和，而且各項小於 $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$，故待證公式也滿足 Fibonacci 遞推式。由 $\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$ 相等時取等號。