算两次

在数学中，算两次是一个常用的证明技巧，常在证明恒等式时被提到。其思想是，对一个具体的量用方法甲来计算，得到的答案是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}$（多项式系数和）

富比尼定理

微积分中的富比尼定理指出重积分在一定条件下可以用不同方法来计算。在这个意义下，算两次也造就了不少分析恒等式。

参见

• 证明组合恒等式的其他组合技巧，如：
  • 母函数
  • 递归关系