朱世傑恆等式

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

$\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}}$