代数/本书课文/求和/组合数求和

利用组合数的性质可以构造出求和公式。

二项式定理

$\sum_{k = 0}^{n} C_{k}^{n} x^{n - k} y^{k} = (x + y)^{n}$

Example

例子：

$\sum_{k = 0}^{n} C_{k}^{n} = 2^{n}$

朱世杰恒等式

$\sum_{k = m}^{n} C_{m}^{k} = C_{m + 1}^{n + 1}$

证明朱世杰恒等式

$\begin{matrix} \sum_{k = m}^{n} C_{m}^{k} & = C_{m}^{m} + C_{m}^{m + 1} + C_{m}^{m + 2} + \dots + C_{m}^{n} \\ = C_{m + 1}^{m + 1} + C_{m}^{m + 1} + C_{m}^{m + 2} + \dots + C_{m}^{n} \\ = C_{m + 1}^{m + 2} + C_{m}^{m + 2} + \dots + C_{m}^{n} \\ = C_{m + 1}^{m + 3} + \dots + C_{m}^{n} = C_{m + 1}^{n + 1} \end{matrix}$

在方幂和上的应用

把多项式转化为组合数，再用朱世杰恒等式求和。^[1]

例子：

\sum_{k = 1}^{n} k^{2}

$\sum_{k = 1}^{n} k^{2} = \sum_{k = 1}^{n} (k^{2} - k + k)$
$= \sum_{k = 1}^{n} (2 C_{2}^{k} + C_{1}^{k}) = 2 C_{3}^{n + 1} + C_{2}^{n + 1}$

求多项式的和

将多项式转化为组合数的过程一般化，对一个多项式求和有如下公式：

证明：

\sum_{k = 1}^{n} p (k) = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & \dots & C_{m + 1}^{n} \end{matrix}) (\begin{matrix} C_{0}^{0} & 0 & \dots & 0 \\ - C_{0}^{1} & C_{1}^{1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (- 1)^{m} C_{0}^{m} & (- 1)^{m - 1} C_{1}^{m} & \dots & C_{m}^{m} \end{matrix}) (\begin{matrix} p (1) \\ p (2) \\ ⋮ \\ p (m + 1) \end{matrix})

^[2]^[3]^[4]

m = \deg (p)

$p (k)$ 为m阶多项式，待定成组合数：

$p (k) = (\begin{matrix} C_{0}^{k - 1} & C_{1}^{k - 1} & \dots & C_{m}^{k - 1} \end{matrix}) (\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{m + 1} \end{matrix})$

代入 $k = 1, 2, \dots, m + 1$ ，得到：

$(\begin{matrix} p (1) \\ p (2) \\ ⋮ \\ p (m + 1) \end{matrix}) = (\begin{matrix} C_{0}^{0} & 0 & \dots & 0 \\ C_{0}^{1} & C_{1}^{1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ C_{0}^{m} & C_{1}^{m} & \dots & C_{m}^{m} \end{matrix}) (\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{m + 1} \end{matrix})$

帕斯卡矩阵的逆等于自身交错地加上负号，于是可直接求出待定系数：

$(\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{m + 1} \end{matrix}) = (\begin{matrix} C_{0}^{0} & 0 & \dots & 0 \\ - C_{0}^{1} & C_{1}^{1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (- 1)^{m} C_{0}^{m} & (- 1)^{m - 1} C_{1}^{m} & \dots & C_{m}^{m} \end{matrix}) (\begin{matrix} p (1) \\ p (2) \\ ⋮ \\ p (m + 1) \end{matrix})$

$p (k) = (\begin{matrix} C_{0}^{k - 1} & C_{1}^{k - 1} & \dots & C_{m}^{k - 1} \end{matrix}) (\begin{matrix} C_{0}^{0} & 0 & \dots & 0 \\ - C_{0}^{1} & C_{1}^{1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (- 1)^{m} C_{0}^{m} & (- 1)^{m - 1} C_{1}^{m} & \dots & C_{m}^{m} \end{matrix}) (\begin{matrix} p (1) \\ p (2) \\ ⋮ \\ p (m + 1) \end{matrix})$
$\sum_{k = 1}^{n} p (k) = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & \dots & C_{m + 1}^{n} \end{matrix}) (\begin{matrix} C_{0}^{0} & 0 & \dots & 0 \\ - C_{0}^{1} & C_{1}^{1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (- 1)^{m} C_{0}^{m} & (- 1)^{m - 1} C_{1}^{m} & \dots & C_{m}^{m} \end{matrix}) (\begin{matrix} p (1) \\ p (2) \\ ⋮ \\ p (m + 1) \end{matrix})$

乘出来的结果也刚好是多项式各阶差分在点1的值。

证明：

\sum_{k = 1}^{n} p (k) = \sum_{j = 1}^{m + 1} C_{j}^{n} Δ^{j - 1} p (1)

^[5]

m = \deg (p), Δ p (n) = p (n + 1) - p (n)

设 $p (k) = \sum_{j = 0}^{m} a_{j} C_{j}^{k - 1} = a_{0} + a_{1} C_{1}^{k - 1} + a_{2} C_{2}^{k - 1} + \dots + a_{m} C_{m}^{k - 1}$

$p (1) = a_{0}$

$Δ C_{l}^{k} = C_{l}^{k + 1} - C_{l}^{k} = C_{l - 1}^{k}$

$Δ^{j} p (k) = a_{j} + a_{j + 1} C_{1}^{k - 1} + a_{j + 2} C_{2}^{k - 1} + \dots + a_{m} C_{m - j}^{k - 1}$

$Δ^{j} p (1) = a_{j}$

$p (k) = \sum_{j = 0}^{m} C_{j}^{k - 1} Δ^{j} p (1)$

$\sum_{k = 1}^{n} p (k) = \sum_{j = 0}^{m} C_{j + 1}^{n} Δ^{j} p (1) = \sum_{j = 1}^{m + 1} C_{j}^{n} Δ^{j - 1} p (1)$

Example

例子：

$\sum_{i = 1}^{n} i^{1} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} \end{matrix}) (\begin{matrix} 1 & 0 \\ - 1 & 1 \end{matrix}) (\begin{matrix} 1 \\ 2 \end{matrix}) = C_{1}^{n} + C_{2}^{n}$

p (k) = k, Δ p (k) = 1

p (1) = 1, Δ p (1) = 1, \sum_{k = 1}^{n} k = C_{1}^{n} + C_{2}^{n}

$\sum_{i = 1}^{n} [a + d (i - 1)] = (\begin{matrix} C_{1}^{n} & C_{2}^{n} \end{matrix}) (\begin{matrix} 1 & 0 \\ - 1 & 1 \end{matrix}) (\begin{matrix} a \\ a + d \end{matrix}) = a C_{1}^{n} + d C_{2}^{n}$ （等差数列求和）

p (k) = a + d (k - 1), Δ p (k) = d

p (1) = a, Δ p (1) = d, \sum_{k = 1}^{n} [a + d (k - 1)] = a C_{1}^{n} + d C_{2}^{n}

$\sum_{i = 1}^{n} i^{2} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 1 & - 2 & 1 \end{matrix}) (\begin{matrix} 1^{2} \\ 2^{2} \\ 3^{2} \end{matrix}) = C_{1}^{n} + 3 C_{2}^{n} + 2 C_{3}^{n}$

p (k) = k^{2}, Δ p (k) = 2 k + 1, Δ^{2} p (k) = 2

p (1) = 1, Δ p (1) = 3, Δ^{2} p (1) = 2, \sum_{k = 1}^{n} k^{2} = C_{1}^{n} + 3 C_{2}^{n} + 2 C_{3}^{n}

$\sum_{i = 1}^{n} i^{3} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} & C_{4}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 \\ 1 & - 2 & 1 & 0 \\ - 1 & 3 & - 3 & 1 \end{matrix}) (\begin{matrix} 1^{3} \\ 2^{3} \\ 3^{3} \\ 4^{3} \end{matrix}) = C_{1}^{n} + 7 C_{2}^{n} + 12 C_{3}^{n} + 6 C_{4}^{n}$

p (k) = k^{3}, Δ p (k) = 3 k^{2} + 3 k + 1, Δ^{2} p (k) = 3 (2 k + 1) + 3 = 6 k + 6, Δ^{3} p (k) = 6, \sum_{k = 1}^{n} k^{3} = C_{1}^{n} + 7 C_{2}^{n} + 12 C_{3}^{n} + 6 C_{4}^{n}

$\sum_{i = 1}^{n} i^{4} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} & C_{4}^{n} & C_{5}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 \\ 1 & - 2 & 1 & 0 & 0 \\ - 1 & 3 & - 3 & 1 & 0 \\ 1 & - 4 & 6 & - 4 & 1 \end{matrix}) (\begin{matrix} 1^{4} \\ 2^{4} \\ 3^{4} \\ 4^{4} \\ 5^{4} \end{matrix}) = C_{1}^{n} + 15 C_{2}^{n} + 50 C_{3}^{n} + 60 C_{4}^{n} + 24 C_{5}^{n}$

$\sum_{i = 1}^{n} i^{5} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} & C_{4}^{n} & C_{5}^{n} & C_{6}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & - 2 & 1 & 0 & 0 & 0 \\ - 1 & 3 & - 3 & 1 & 0 & 0 \\ 1 & - 4 & 6 & - 4 & 1 & 0 \\ - 1 & 5 & - 10 & 10 & - 5 & 1 \end{matrix}) (\begin{matrix} 1^{5} \\ 2^{5} \\ 3^{5} \\ 4^{5} \\ 5^{5} \\ 6^{5} \end{matrix}) = C_{1}^{n} + 31 C_{2}^{n} + 180 C_{3}^{n} + 390 C_{4}^{n} + 360 C_{5}^{n} + 120 C_{6}^{n}$

$\sum_{i = 1}^{n} (2 i - 1)^{2} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 1 & - 2 & 1 \end{matrix}) (\begin{matrix} 1^{2} \\ 3^{2} \\ 5^{2} \end{matrix}) = C_{1}^{n} + 8 C_{2}^{n} + 8 C_{3}^{n}$

$\sum_{i = 1}^{n} (3 i - 2)^{3} = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} & C_{4}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 \\ 1 & - 2 & 1 & 0 \\ - 1 & 3 & - 3 & 1 \end{matrix}) (\begin{matrix} 1^{3} \\ 4^{3} \\ 7^{3} \\ 1 0^{3} \end{matrix}) = C_{1}^{n} + 63 C_{2}^{n} + 216 C_{3}^{n} + 162 C_{4}^{n}$

$\sum_{i = 1}^{n} (i^{3} + 2 i + 1) = (\begin{matrix} C_{1}^{n} & C_{2}^{n} & C_{3}^{n} & C_{4}^{n} \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 \\ 1 & - 2 & 1 & 0 \\ - 1 & 3 & - 3 & 1 \end{matrix}) (\begin{matrix} 4 \\ 13 \\ 34 \\ 73 \end{matrix}) = 4 C_{1}^{n} + 9 C_{2}^{n} + 12 C_{3}^{n} + 6 C_{4}^{n}$

范德蒙恒等式

$\sum_{k = 0}^{n} C_{k}^{a} C_{n - k}^{b} = C_{n}^{a + b}$

证明范德蒙恒等式

甲班有a个同学，乙班有b个同学，从两个班中选出n名有 $C_{n}^{a + b}$ 种方法。
从甲班选k名，从乙班选n-k名有 $C_{k}^{a} C_{n - k}^{b}$ 种方法，考虑所有情况k=0,1,...,n，从两个班中选出n名有 $\sum_{k = 0}^{n} C_{k}^{a} C_{n - k}^{b}$ 种方法。^[6]

参考资料

↑ 田达武. 朱世杰恒等式及其应用. 数学教学通讯. 2009, (36).
↑ 陶家元. 高阶等差数列的前n项求和. 成都大学学报(自然科学版). 1999, (1).
↑ 黄婷车茂林彭杰张莉. 自然数幂和通项公式证明的新方法. 内江师范学院学报. 2011, (8).
↑ 黄嘉威. 方幂和及其推广和式. 数学学习与研究. 2016, (7).
↑ Károly Jordán. Calculus of Finite Differences (PDF). 1950.
↑ 李松槐杨伏香. 用数学模型证明范得蒙(Vandermonde)恒等式. 河南教育学院学报(自然科学版). 1999, (2).

[1] 田达武. 朱世杰恒等式及其应用. 数学教学通讯. 2009, (36).

[2] 陶家元. 高阶等差数列的前n项求和. 成都大学学报(自然科学版). 1999, (1).

[3] 黄婷车茂林彭杰张莉. 自然数幂和通项公式证明的新方法. 内江师范学院学报. 2011, (8).

[4] 黄嘉威. 方幂和及其推广和式. 数学学习与研究. 2016, (7).

[5] Károly Jordán. Calculus of Finite Differences (PDF). 1950.

[6] 李松槐杨伏香. 用数学模型证明范得蒙(Vandermonde)恒等式. 河南教育学院学报(自然科学版). 1999, (2).

[1]

[2]

[3]

[4]

[5]

[6]