朱世杰恒等式

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

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

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

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

证明

递归方法

欲证

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

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

组合方法

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

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

${\displaystyle \sum _{k=r}^{n}{\binom {k-1}{r-1}}={\binom {n}{r}}}$^[2]

应用

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

${\displaystyle \sum _{i=1}^{n}i=\sum _{i=1}^{n}{\binom {i}{1}}={\binom {n+1}{2}}}$

${\displaystyle \sum _{i=1}^{n}i(i+1)=2\sum _{i=1}^{n}{\binom {i+1}{2}}=2{\binom {n+2}{3}}}$^[3]