Monthly Archives: December 2013

用組合數學來證明恆等式

Leave a reply

證明 \sum_{k=1}^{n}k\binom{n}{k}=n2^{n-1} ，其中 n 是正整數。

這道題目是以前香港高考純數試卷中的常客。

考評局的評分標準老師會教我們考慮二項式定理（Binomial Theorem），得
(x+1)^n=\sum_{k=0}^{n}\binom{n}{k}x^k

接著，把方程式的兩邊同時對 x 微分，得
n(x+1)^{n-1}=\sum_{k=1}^{n}k\binom{n}{k}x^{k-1}

最後，代入 x=1 即完成證明。

或者大家未接觸過純數，讓我們試試用組合數學（Combinatorics）來證明。

先想像一下這個情景：我們要由 n 人之中選出一些人（最少一人、最多全部人）來成立一個委員會，再委派委員會內的其中一人當會長。委員會的組合方法有多少種呢？

根據定義，由 n 人選出 k 人的方法有 \binom{n}{k} 種；而由 k 人之中選出一人當會長的方法有 k 種。因為 k 的取值範圍是由 1 到 n，所以根據基本的組合數學法則，總共有 \sum_{k=1}^{n}k\binom{n}{k} 種委派方法，這是恆等式的左方。

另一方面，由 n 人中選出一人當委員會的會長，選法有 n 種；而會長以外的 n-1 人中，每個人都有兩種可能性（會員或非會員），選法有 2^{n-1} 種。因此，總共有 n2^{n-1} 種委派方法，這是恆等式的右方。

以上兩種委派方法應該會得出相等答案，因此我們欲證明的恆等式成立。這個就是用組合數學來證明恆等式的例子，而這類證明則被稱為組合證明（Combinatorial Proof）。

一般來說，組合證明的做法就是先虛構一個與組合數學有關的情景，接著證明恆等式的兩邊都是（由兩種不同的方向找出來）這個問題的答案。

還有很多恆等式有組合證明，如 \binom{m+n}{r}= \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} 和 \binom{n+1}{r+1}= \sum_{k=r}^{n}\binom{k}{r} 。

組合證明華麗和生動有趣，比數論證明可以更清楚展示恆等式背後的意義。當然，要虛構一個情景出來，需要很強的觀察力和創意，絕對不是一件容易的事。

延伸閱讀：Notes on Combinatorial Arguments from University of Victoria