朱世傑恆等式

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

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