8. 計數、歸納法與二項式定理

設 $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$ 的對應歸納版本。

學習目標與定義

計算有序與無序選擇的數量，證明有限二項式定理，並將系數與恆等式聯繫起來。對正整數，令 $n! =1\cdot2\cdots n$，並定義 $0!=1$。對整數 $0\le k\le n$，二項式系數

$$\binom nk=\frac{n!}{k!(n-k)!}$$

計數一個 $n$ 元集合的 $k$ 元子集。理由是：先按次序選出 $k$ 個不同元素，有 $n(n-1)\cdots(n-k+1)$ 種方法；每個子集恰好出現 $k!$ 種次序。對 $0\le k\le n$ 以外的整數，定義 $\binom nk=0$。

乘法原理在每階段都有所述數目的後續選擇時，將各階段選擇數相乘。加法原理將互斥方案的數量相加。若方案重疊，相加會重複計數；因此有限集合的容斥從 $|A\cup B|=|A|+|B|-|A\cap B|$ 開始。

定理：帕斯卡恆等式與二項式定理

對整數 $n\ge0$，

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

該多項式恆等式對所有實數或複數 $a,b$ 成立。

證明。 從一個含指定元素的集合中選 $k$ 個元素，可分為包含該元素（從其餘 $n$ 個中選 $k-1$ 個）和不包含該元素（從其餘 $n$ 個中選 $k$ 個）兩類。這兩類互斥且窮盡，故證明帕斯卡恆等式，包括按零約定處理的邊界情況。二項式定理在 $n=0$ 成立。假設它在 $n$ 成立，乘以 $a+b$；$a^{n+1-k}b^k$ 的系數有 $\binom nk$ 和 $\binom n{k-1}$ 兩部分，由帕斯卡恆等式相加為 $\binom{n+1}k$。這證明歸納步驟，也證明所有非負整數情況。

定理是有限的。若將 $n$ 換成非整數，得到的是無窮二項式級數，需要本歸納證明未提供的收斂定理。

例題

含負項的系數。 在 $(2x-1)^5$ 中，$x^3$ 的系數使用三個 $2x$ 和兩個 $-1$，所以是 $\binom53 2^3(-1)^2=80$。先數出 $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$，故偶數大小與奇數大小的子集一樣多。組合證明可切換一個固定元素的包含狀態，將每個偶數子集與一個奇數子集配對。

無序選擇。 從七人中選三人委員會，有 $\binom73=35$ 種方法。若分別指定主席、秘書和司庫，則有 $7\cdot6\cdot5=210$ 種，因為職位區分了不同順序。

分層練習

1. 基礎。 計算 $\binom82$ 並解釋它計數甚麼。
2. 核心。 求 $(1-3x)^6$ 中 $x^4$ 的系數。
3. 核心。 從一副標準的 52 張牌中選五張，恰好含兩張 A 的手牌有多少種？說明為何各因子相乘。
4. 證明。 對 $n\ge1$，通過計數一個子集及其中一個指定成員，證明 $\sum_{k=0}^n k\binom nk=n2^{n-1}$。

詳解

1. $\binom82=8\cdot7/2=28$，它計數八元集合中不同元素組成的無序對。
2. 選四個 $-3x$ 和兩個 $1$，系數為 $\binom64(-3)^4=15\cdot81=1215$。
3. 從四張 A 中選兩張，從 48 張非 A 中選三張，得到 $\binom42\binom{48}3$。每副手牌都唯一分成 A 和非 A 兩部分；一部分的每個允許選擇都可以與另一部分的每個允許選擇配對。因此可相乘，不需要假設概率模型。
4. 對每個大小 $k$，有 $\binom nk$ 個子集及 $k$ 種指定成員選擇，得到左邊。另一種方法是先用 $n$ 種方法選擇指定成員，再從剩下 $n-1$ 個元素中任選子集，有 $2^{n-1}$ 種。兩邊計數完全相同的對子，故恆等式成立。

總結與術語

排列是有序選擇；組合是無序選擇。歸納法證明初始情形和每一步到下一步的蘊含，而不是只檢驗幾個例子。系數是乘以指定冪的標量。有限二項式展開來自精確計數或歸納；任何無窮推廣都需要另行分析收斂和餘項。