算兩次

在數學中，算兩次是一個常用的證明技巧，常在證明恆等式時被提到。其思想是，對一個具體的量用方法甲來計算，得到的答案是A，而用方法乙則得到B，那麼等式A = B成立。此思想雖然明顯，但在實際使用時由於方法甲與方法乙通常有明顯的差異，因此能把兩個表面上相去甚遠的式子聯繫起來。算兩次產生過很多漂亮的證明。

組合恆等式

组合數學中的算兩次是一种组合证明方法。我們可以對同一個組合計數問題從兩個不同的方面去觀察，從而得到兩個表達式，其值卻相同。例如以下問題：

設 n 為給定的正整數。假如你要創造一種語言，其中的字母只有 ※ 和 ◎ 兩種，而每個詞語總是由 n 個字母組成，那最多可以有多少個不同的詞語？

甲：由於詞語中任一位置都可以自由地選擇※或◎中的任何一個，所以答案是 2 × 2 × ... × 2 = 2ⁿ。

乙：如果進一步規定◎正好出現 k 次，那麼符合要求的單詞就只有 n 取 k 那麼多個了。但k 可以是 0, 1, 2, ..., n 的任何一個，因此總計起來即為 $\sum _{k=0}^{n}{n \choose k}$ ，其中 ${n \choose k}$ 是組合數（n取k）。

兩種方法都得到了正確的表達式，因此$\sum _{k=0}^{n}{n \choose k}=2^{n}$。

更多例子

除了以上的二項式系數和，以下這些基本的組合恆等式也可以用算兩次的辦法來論證（但對不同的讀者來說不一定是最簡單的辦法）：

• ${n \choose k}={n \choose n-k}$

• ${n+1 \choose k}={n \choose k-1}+{n \choose k}$

• $\sum _{k=1}^{n}k{n \choose k}=n2^{n-1}$

• $\sum _{k=0}^{n}{a \choose k}{b \choose n-k}={a+b \choose n}$（來自超幾何分布的等式）

• $\sum _{0\leq m_{i}\leq n;m_{1}+m_{2}+...+m_{r}=n}{\frac {n!}{m_{1}!m_{2}!...m_{r}!}}=r^{n}$（多項式系數和）

富比尼定理

微積分中的富比尼定理指出重積分在一定條件下可以用不同方法來計算。在這個意義下，算兩次也造就了不少分析恆等式。

參見

• 證明組合恆等式的其他組合技巧，如：
  • 母函數
  • 遞歸關係