朱世杰恒等式

朱世杰恒等式是组合数的一阶求和公式。元朝数学家朱世杰在《四元玉鉴》中，利用垛积术、招差术给出：

$\sum _{i=a}^{n}{\binom {i}{a}}={\binom {n+1}{a+1}}$，

或以$m-1$代$n$再与上式作差，写成：

$\sum _{i=m}^{n}{\binom {i}{a}}={\binom {n+1}{a+1}}-{\binom {m}{a+1}}$。

证明

递归方法

欲证

${\binom {m}{a+1}}+{\binom {m}{a}}+{\binom {m+1}{a}}...+{\binom {n}{a}}={\binom {n+1}{a+1}}$，

可以反复使用帕斯卡法则合并左式首两项。

组合方法

从$n$元集$S=\{a_{1},a_{2},a_{3},...,a_{n}\}$选$r$个元素，有${\binom {n}{r}}$种方法。

必有$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 {n}{r}}$

应用

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

$\sum _{i=1}^{n}i=\sum _{i=1}^{n}{\binom {i}{1}}={\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}}$