我們想要使用歸納原則來證明。
歸納起始點：
n = 1: B(1, 1) = 1!/(1! ⋅ 0!) = 1 = 1 ⋅ 20
歸納步驟：
我們先假設，當任意自然數n = k 時(18) 式成立，也就是
B(k, 1) + 2B(k, 2) + 3B(k, 3) + ⋯ + kB(k, k) = k2k-1
為了方便稱呼，我們將左式簡稱為S(k)。於是，
S(k + 1) = B(k + 1, 1) + 2B(k + 1, 2) + 3B(k + 1, 3) + ⋯ +
(k + 1)B(k + 1, k + 1)
基本的概念就在於使用到下面這個分解：
B(n, k) = B(n − 1, k) + B(n − 1, k − 1)
把等號左右兩邊分開計算，便可驗證上面的式子。我們再次看到富比尼原理發揮作用。根據二項式係數的定義，左式是指從n 個人中選出k 人（k 人小組）的方法數。右式的解釋為：選出任何一人P。B(n − 1, k) 是選出不含P 在內的k 人小組的方法數，而B(n − 1, k − 1) 則是包含P 在內的k 人小組的方法數。兩者之和便是從n 人中選出k 人小組的方法數。
在這一步的考慮之後，我們可以把剛才的式子重新寫成：
S(k + 1) = [B(k, 0) + B(k, 1)] + 2[B(k, 1) + B(k, 2)] + ⋯ + k[B(k, k – 1)
+ B(k, k)] + (k + 1)B(k, k)
= B(k, 0) + 3B(k, 1) + 5B(k, 2) + ⋯ + (2k + 1)B(k, k)
= [B(k, 0) + B(k, 1) + B(k, 2) + ⋯ + B(k, k)] + 2S(k)
= 2k + 2k ⋅ 2k–1
= (k + 1) ⋅ 2k
在倒數第二步，我們使用了101 頁的(10) 式來化簡中括號裡的式子。
這是個完整的證明。但我們在這個例子多停留一會兒。受到富比尼原理發揮用的鼓勵，我們決定替複雜得多的(18) 式尋找一個類似的論證：一個比數學
歸納法更有創意的另類證法。
為此我們先自問以下的問題：從n 人當中選出k 人小組，而k 人小組裡有一人是主席，可有多少種選法？ k 人小組可以選第1 到第n 個成員，而k 人小組中的任何成員均可當主席。答案：選出k 人小組一共有B(n, k) 種選法，而對於每種選法，又有k 種選出主席的方法，根據乘法原理，就有kB(n, k) 種可能的選法。好啦，k可以從1任意變化到n。這就產生了kB(n, k)從1到n的加總。這也正是(18)式的左半邊。太好了。那該如何求出右半邊呢？十分簡單。我們可以換個方式計算，先從n 人中選出主席，這一共有n 種選法。然後再從剩下的n − 1 人中選出k 人小組的其他成員。從n − 1 人中，不是被選進k 人小組，就是被排除在外，所以對每個人來說都有兩種可能。對n − 1 人而言，根據乘法原理，就有2n-1 種可能。因此，同樣是根據乘法原理，總共會有n2n-1 種選法。十分漂亮的證法，也是公式(18) 的第二種證明方法。
還有一個同樣機智、在某方面看來甚至更漂亮的方式來證明(18) 式：透過S(n)/2n。這個比率用文字來敘述，意思為含有n 個元素的集合{1, 2, 3, ⋯, n} 的所有子集合的平均大小。這是因為，有k 個元素的子集合恰好有B(n, k) 個，而所有的子集合總共有2n 個。為什麼呢？因為對於n 個元素的每個元素來說，也永遠有兩種可能：屬於某個子集，或不屬於某個子集。
現在我們可以把任何一個子集跟其餘集配對。成對的集合一共含有n 個元素，平均每個集合有n/2 個元素。由於每對集合都有n/2 個元素，所以S(n)/2n = n/2正是(18) 式所說的內容。很特別吧！
本文經授權轉載自漫遊者文化《德國一流大學教你數學家的22個思考工具》
