朱世杰恒等式

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

${\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]