朱世杰恒等式

朱世杰恒等式是组合数的一阶求和公式。元朝數學家朱世傑在《四元玉鑒》中，利用垛積術、招差術給出：

:\sum_{i = a}^n \binom{i}{a} = \binom{n + 1}{a+1}，
或以m-1代n再與上式作差，寫成：
: \sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1} 。

证明
递归方法
欲證
: \binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1} ，
可以反覆使用帕斯卡法則合併左式首兩項。

组合方法
从n元集S=\{a_1,a_2,a_3,...,a_n\}选r个元素，有\binom nr种方法。

必有a_1时，在n-1个元素中选r-1个元素，排除a_1，必有a_2时，在n-2个元素中选r-1个元素，排除a_2，如此类推，直到必有a_{n-r+1}时，在r-1个元素中选r-1个元素。

\sum_{k=r}^n \binom {k-1}{r-1} =\binom nr

应用
朱世杰恒等式可应用于等幂求和问题。例如：

:\sum_{i=1}^n i=\sum_{i=1}^n \binom i1=\binom {n+1}2

:\sum_{i=1}^n i(i+1)=2\sum_{i=1}^n \binom {i+1}2=2\binom {n+2}3

参考资料