6. 歸納法與二項式定理

學習目標與準備

公式可能在幾個例子中正確，之後卻失敗。本章區分證據與證明。你將寫出具有整數定義域的命題，組織基礎情形與歸納步驟，僅在允許處使用假設，並推導和應用二項式定理。第 5 章提供有限數列和代數恆等式；本章不假設概率論知識。

6.1 歸納法究竟證明甚麼

設 $P(n)$ 是關於整數 $n\ge n_0$ 的陳述，$n_0$ 固定。數學歸納法說明：

1. 證明基礎情形 $P(n_0)$。
2. 對任意整數 $k\ge n_0$，假設 $P(k)$，並證明 $P(k+1)$。
3. 得出對每個整數 $n\ge n_0$ 都有 $P(n)$。

第 2 步的假設是歸納假設，它是條件性的，不是預先假設最終定理成立。基礎情形啓動鏈條，蘊含則將任意有效一環延伸到下一環。

可用非負整數的最小元素性質說明：若有反例，則存在最小反例 $m\ge n_0$。基礎情形排除 $n_0$，於是 $m-1\ge n_0$ 不是反例，歸納步驟迫使 $P(m)$ 成立，矛盾。

對於任意整數起點 $n_0$，將指標平移為 $m-n_0\ge0$，即可用最小元素性質證明上面的最小反例步驟。

反過來，正整數上的普通歸納法蘊含最小元素性質。假設非空集合 $S\subseteq\{1,2,3,\ldots\}$ 沒有最小元素。令 $P(n)$ 表示 $1,\ldots,n$ 均不屬於 $S$。若 $1\in S$，它就是最小元素，故 $P(1)$ 成立。若 $P(k)$ 成立而 $k+1\in S$，則 $k+1$ 是 $S$ 的最小元素，矛盾。因此 $P(k)\Rightarrow P(k+1)$。歸納法給出每個正整數 $n$ 都滿足 $P(n)$，於是 $S$ 為空，與其非空假設矛盾。所以每個非空正整數集合都有最小元素。用 $n\mapsto n-n_0+1$ 平移指標，即得任意整數起點 $n_0$ 的對應歸納版本。

不要在步驟中假設準備證明的命題對所有整數成立。只假設聲明的 $P(k)$（或強歸納法中明確允許的先前情形），再推導下一情形。歸納法證明整數指標上的陳述，不自動涵蓋所有實數。

例 1——邊界移動的和。 對每個正整數 $n$，

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

當 $n=1$，兩邊均為 $1$。假設等式對任意 $k\ge1$ 成立，則

$$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2,$$

恰是 $n=k+1$ 時所需公式。左邊只增加一項，而不是無解釋的新表達式。

6.2 選擇陳述並使用假設

例 2——重複增加的遞推式。 假設 $B_0=0$、$B_{n+1}=rB_n+c$，其中 $r,c$ 是固定實數。聲稱

$$B_n=c\sum_{j=0}^{n-1}r^j\quad(n\ge1).$$

基礎情形 $n=1$ 給出 $B_1=c$。假設公式對 $k\ge1$ 成立，遞推式給出

$$B_{k+1}=rc\sum_{j=0}^{k-1}r^j+c =c\left(1+\sum_{j=1}^{k}r^j\right)=c\sum_{j=0}^{k}r^j.$$

故命題對所有正整數成立。使用第 5 章的有限幾何和，$r\ne1$ 時得到 $c(1-r^n)/(1-r)$，$r=1$ 時得到 $nc$。歸納證明本身沒有除以 $1-r$，因此也覆蓋例外公比。

例 3——整除性。 當 $n\ge1$，$7^n-1$ 被 $6$ 整除。在 $n=1$ 它等於 $6$。若對整數 $m$ 有 $7^k-1=6m$，則

$$7^{k+1}-1=7(7^k-1)+6=6(7m+1).$$

乘數 $7m+1$ 是整數，這證明整除性，而不只是觀察表達式為偶數。

有時加強陳述有助于歸納。證明遞推界時，較弱的目標可能沒有提供傳遞到下一步所需信息。初等證明中，應先明確寫出 $P(k+1)$，再確定遞推式需要甚麼估計。不能以“模式顯然繼續”替代失敗步驟。

6.3 不等式與乘數符號

對實數 $t\ge-1$ 和整數 $n\ge1$，Bernoulli 不等式為

$$(1+t)^n\ge1+nt.$$

$n=1$ 處顯然取等。從 $k\ge1$ 出發，乘以 $1+t\ge0$ 保持所假設不等式的方向：

$$(1+t)^{k+1}\ge(1+kt)(1+t) =1+(k+1)t+kt^2\ge1+(k+1)t.$$

非負餘項證明下一情形。乘數條件不可少；乘以負數會反轉不等號。對 $t>0$、$n\ge2$，不等式嚴格，因為 $k=1$ 的步驟已經加入正數 $t^2$。

例 4——下界不等於精確值。 某假設量在 $10$ 個相等週期中每期增加 $2\%$。其乘數滿足 $1.02^{10}\ge1+10(0.02)=1.2$，故增加至少 $20\%$，不恰好是 $20\%$。精確乘數由複合表達式給出。歸納無需小數近似即可證明可靠比較。

錯誤分析。 $2^n\ge n^2$ 在 $n=1,2$ 成立，卻在 $n=3$ 失敗，因為 $8<9$。正確歸納證明不可能覆蓋所有 $k\ge1$。它對 $n\ge4$ 成立：在 $4$ 取等，且對 $k\ge4$，

$$2^{k+1}\ge2k^2\ge(k+1)^2,$$

因為 $2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2>0$。起始範圍是定理的一部分。

6.4 二項式系數與 Pascal 恆等式

對整數 $n\ge0$、$0\le k\le n$，定義

$$\binom nk=\frac{n!}{k!(n-k)!},\qquad 0!=1.$$

它計算從 $n$ 個不同對象中選取 $k$ 個的方式：有 $n(n-1)\cdots(n-k+1)$ 個有序選擇，每個無序選擇出現 $k!$ 個順序。特別地 $\binom n0=\binom nn=1$、$\binom nk=\binom n{n-k}$。

對 $1\le k\le n$，Pascal 恆等式為

$$\binom n{k-1}+\binom nk=\binom{n+1}k.$$

無需階乘運算即可說明：在 $n+1$ 個對象中特別標記一個。$k$ 元選擇要麼包含它，此時其餘 $k-1$ 個從 $n$ 個中選；要麼不包含它，此時所有 $k$ 個從 $n$ 個中選。兩種情況互斥且窮盡。也可將兩個階乘分式通分至 $k!(n+1-k)!$；分子因子之和為 $k+(n+1-k)=n+1$。

6.5 推導二項式定理

對非負整數 $n$ 和實數 $a,b$，

$$(a+b)^n=\sum_{k=0}^{n}\binom nk a^{n-k}b^k.$$

此多項式恆等式中，指數為零的冪代表常數因子 $1$，包括 $a=0$ 或 $b=0$ 時。這是多項式求值約定，不是聲稱每個極限表達式 $0^0$ 都有指定值。

歸納證明。 當 $n=0$，兩邊均為 $1$。假設公式對 $n$ 成立，乘以 $a+b$。一部分貢獻 $\binom nk a^{n+1-k}b^k$；另一部分換指標後貢獻 $\binom n{k-1}a^{n+1-k}b^k$。中間項用 Pascal 恆等式合併，兩端保留 $a^{n+1}$ 和 $b^{n+1}$。結果恰是 $n+1$ 的公式。

也可直接理解：在 $n$ 個 $(a+b)$ 的乘積中，含 $k$ 個 $b$ 和 $n-k$ 個 $a$ 的項由選擇哪 $k$ 個因子貢獻 $b$ 而產生，共有 $\binom nk$ 種選擇。這同時解釋系數和指數。

整數條件很重要。例如 $(1+x)^{1/2}$ 不是兩項多項式。無窮二項展開需要額外收斂理論，不是此處證明的有限定理。

例 5——只提取所需系數。 在 $(2x-3)^5$ 中，含 $x^3$ 的項使用 $k=2$ 個 $-3$：

$$\binom52(2x)^3(-3)^2=720x^3.$$

故系數為 $720$。負項平方，符號為正。

例 6——含倒數冪的系數。 在 $(x^2+1/x)^6$ 中（$x\ne0$），一般項為 $\binom6k x^{12-3k}$。常數項出現在 $12-3k=0$，故 $k=4$，常數項為 $\binom64=15$。這是 Laurent 表達式而非 $x$ 的多項式，但對每個非零 $x$，有限二項式定理適用於兩個有定義的實數輸入。

令 $a=b=1$ 得 $\sum_{k=0}^{n}\binom nk=2^n$。對 $n\ge1$，令 $a=1,b=-1$ 得 $\sum_{k=0}^{n}(-1)^k\binom nk=0$。後者排除 $n=0$，其和為 $1$。

6.6 分級練習

基礎

1. 寫出證明對所有整數 $n\ge3$ 成立所需的基礎情形和歸納步驟。
2. 計算 $\binom62$ 和 $\binom64$，解釋為甚麼相同。
3. 精確展開 $(x+2)^4$。

核心

4. 證明對每個正整數 $n$，$1+3+\cdots+(2n-1)=n^2$。
5. 證明對每個整數 $n\ge1$，$3^n-1$ 被 $2$ 整除。
6. 用歸納法證明 $1+2+4+\cdots+2^{n-1}=2^n-1$，不要引用幾何和公式。
7. 求 $(3x-1)^5$ 中 $x^2$ 的系數。
8. 對 $x\ne0$，求 $(x^3-2/x)^8$ 的常數項。

綜合

9. 學生聲稱任何 $n$ 個彩色計數物的集合只有一種顏色：“$n=1$ 成立；對 $(n+1)$ 個，分別去掉第一個和最後一個，兩個 $n$ 元子集各自只有一種顏色，所以所有對象同色。”指出失敗步驟。
10. 用有限二項式定理證明 $t\ge0$ 時 $(1+t)^5\ge1+5t+10t^2$。對每個 $-1\le t<0$ 同樣成立嗎？
11. 用歸納法證明 $\sum_{j=1}^{n}j^2=n(n+1)(2n+1)/6$。
12. 對 $n\ge1$，用選擇論證證明 $\sum_{k=0}^{n}k\binom nk=n2^{n-1}$。

6.7 完整解答

1. 驗證 $P(3)$。然後對任意整數 $k\ge3$，假設 $P(k)$ 並推導 $P(k+1)$。僅有 $1$ 處基礎情形而缺少中間連接情形，不能自行從 $3$ 啓動鏈條。
2. 兩者均為 $6!/(2!4!)=15$。選擇兩個選中對象等價於選擇四個被省略對象。
3. 系數為 $1,4,6,4,1$，故 $(x+2)^4=x^4+8x^3+24x^2+32x+16$。
4. 基礎情形為 $1=1^2$。若前 $k$ 個奇數和為 $k^2$，加入下一個 $2k+1$ 得 $k^2+2k+1=(k+1)^2$。
5. $1$ 處 $3-1=2$。若 $3^k-1=2m$，則 $3^{k+1}-1=3(3^k-1)+2=2(3m+1)$，為偶整數。
6. $1$ 處 $1=2-1$。若到 $2^{k-1}$ 的和為 $2^k-1$，加入 $2^k$ 得 $2^{k+1}-1$。
7. 恰選兩個 $3x$ 和三個 $-1$，系數為 $\binom52 3^2(-1)^3=-90$。
8. 一般項為 $\binom8k(-2)^k x^{24-4k}$。指數在 $k=6$ 時為零，得到 $\binom86(-2)^6=28(64)=1792$。
9. 從一個推到兩個對象時，兩個單元素子集沒有共同成員，沒有共享對象使顏色相等。所提步驟恰在第一環失敗；後續重疊不能修復它。
10. 被省略部分為 $10t^3+5t^4+t^5=t^3(10+5t+t^2)$，在 $t\ge0$ 時非負。對 $-1\le t<0$，$t^3<0$ 且 $10+5t+t^2>0$，故所提不等式嚴格反向；例如 $t=-1$ 時它會寫成 $0\ge6$。
11. $1$ 處公式給出 $1$。在所假設和上加 $(k+1)^2$，得 $k(k+1)(2k+1)/6+(k+1)^2=(k+1)(2k^2+7k+6)/6=(k+1)(k+2)(2k+3)/6$，恰是 $k+1$ 情形。
12. 計數數對 $(S,s)$，其中 $S$ 是 $n$ 元集的子集，$s\in S$ 被標記。按子集大小計數有 $\sum_k k\binom nk$ 種。也可先以 $n$ 種方式選 $s$，再獨立選擇其他 $n-1$ 個元素中哪些屬於 $S$，有 $2^{n-1}$ 種。兩種計數相等。

總結與遷移

歸納證明要聲明整數範圍、起始情形，以及在每個所需環節有效的蘊含。整除證明展示整數倍；不等式證明論證每個乘數的符號。二項式系數計算選擇數，Pascal 恆等式合併相鄰系數，有限二項式定理可由乘法或選擇推導。提取系數先是指數問題，再是算術問題。