朱世杰恒等式

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

\sum_{i = a}^{n} (\binom{i}{a}) = (\binom{n + 1}{a + 1})

^[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})$ ^[2]

应用

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

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

^[3]

参考资料

Template:Reflist

[1] Template:Cite journal

[2] Template:Cite journal

[3] Template:Cite journal

[1]

[2]

[3]

朱世杰恒等式

目录

证明

递归方法

组合方法

应用

参考资料

导航菜单

朱世杰恒等式

证明

递归方法

组合方法

应用

参考资料

导航菜单

搜索