# 代數/本書課文/求和/組合數求和

## 二項式定理

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

${\displaystyle \sum _{k=0}^{n}C_{k}^{n}=2^{n}}$

## 朱世杰恒等式

${\displaystyle \sum _{k=m}^{n}C_{m}^{k}=C_{m+1}^{n+1}}$

 证明朱世杰恒等式 {\displaystyle {\begin{aligned}\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{aligned}}}

### 在方冪和上的應用

 例子：${\displaystyle \sum _{k=1}^{n}k^{2}}$ ${\displaystyle \sum _{k=1}^{n}k^{2}=\sum _{k=1}^{n}(k^{2}-k+k)}$ ${\displaystyle =\sum _{k=1}^{n}(2C_{2}^{k}+C_{1}^{k})=2C_{3}^{n+1}+C_{2}^{n+1}}$

### 求多項式的和

 证明：${\displaystyle \sum _{k=1}^{n}p(k)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&\cdots &C_{m+1}^{n}\end{pmatrix}}{\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\-C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\(-1)^{m}C_{0}^{m}&(-1)^{m-1}C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}}$[2][3][4] ${\displaystyle m=\deg(p)}$ ${\displaystyle p(k)}$為m階多項式，待定成組合數： ${\displaystyle p(k)={\begin{pmatrix}C_{0}^{k-1}&C_{1}^{k-1}&\cdots &C_{m}^{k-1}\end{pmatrix}}{\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+1}\end{pmatrix}}}$ 代入${\displaystyle k=1,2,\dots ,m+1}$，得到： ${\displaystyle {\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}={\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\C_{0}^{m}&C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+1}\end{pmatrix}}}$ 帕斯卡矩陣的逆等於自身交錯地加上負號，於是可直接求出待定系數： ${\displaystyle {\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+1}\end{pmatrix}}={\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\-C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\(-1)^{m}C_{0}^{m}&(-1)^{m-1}C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}}$ ${\displaystyle p(k)={\begin{pmatrix}C_{0}^{k-1}&C_{1}^{k-1}&\cdots &C_{m}^{k-1}\end{pmatrix}}{\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\-C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\(-1)^{m}C_{0}^{m}&(-1)^{m-1}C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}}$ ${\displaystyle \sum _{k=1}^{n}p(k)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&\cdots &C_{m+1}^{n}\end{pmatrix}}{\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\-C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\(-1)^{m}C_{0}^{m}&(-1)^{m-1}C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}}$ 乘出來的結果也剛好是多項式各階差分在點1的值。
 证明：${\displaystyle \sum _{k=1}^{n}p(k)=\sum _{j=1}^{m+1}C_{j}^{n}\Delta ^{j-1}p(1)}$[5]${\displaystyle m=\deg(p),\Delta p(n)=p(n+1)-p(n)}$ 設${\displaystyle 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}}$ ${\displaystyle p(1)=a_{0}}$ ${\displaystyle \Delta C_{l}^{k}=C_{l}^{k+1}-C_{l}^{k}=C_{l-1}^{k}}$ ${\displaystyle \Delta ^{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}}$ ${\displaystyle \Delta ^{j}p(1)=a_{j}}$ ${\displaystyle p(k)=\sum _{j=0}^{m}C_{j}^{k-1}\Delta ^{j}p(1)}$ ${\displaystyle \sum _{k=1}^{n}p(k)=\sum _{j=0}^{m}C_{j+1}^{n}\Delta ^{j}p(1)=\sum _{j=1}^{m+1}C_{j}^{n}\Delta ^{j-1}p(1)}$

${\displaystyle \sum _{i=1}^{n}i^{1}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}\end{pmatrix}}{\begin{pmatrix}1&0\\-1&1\end{pmatrix}}{\begin{pmatrix}1\\2\end{pmatrix}}=C_{1}^{n}+C_{2}^{n}}$

${\displaystyle p(k)=k,\Delta p(k)=1}$
${\displaystyle p(1)=1,\Delta p(1)=1,\sum _{k=1}^{n}k=C_{1}^{n}+C_{2}^{n}}$

${\displaystyle \sum _{i=1}^{n}[a+d(i-1)]={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}\end{pmatrix}}{\begin{pmatrix}1&0\\-1&1\end{pmatrix}}{\begin{pmatrix}a\\a+d\end{pmatrix}}=aC_{1}^{n}+dC_{2}^{n}}$（等差數列求和）

${\displaystyle p(k)=a+d(k-1),\Delta p(k)=d}$
${\displaystyle p(1)=a,\Delta p(1)=d,\sum _{k=1}^{n}[a+d(k-1)]=aC_{1}^{n}+dC_{2}^{n}}$

${\displaystyle \sum _{i=1}^{n}i^{2}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0\\-1&1&0\\1&-2&1\end{pmatrix}}{\begin{pmatrix}1^{2}\\2^{2}\\3^{2}\end{pmatrix}}=C_{1}^{n}+3C_{2}^{n}+2C_{3}^{n}}$

${\displaystyle p(k)=k^{2},\Delta p(k)=2k+1,\Delta ^{2}p(k)=2}$
${\displaystyle p(1)=1,\Delta p(1)=3,\Delta ^{2}p(1)=2,\sum _{k=1}^{n}k^{2}=C_{1}^{n}+3C_{2}^{n}+2C_{3}^{n}}$

${\displaystyle \sum _{i=1}^{n}i^{3}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}1^{3}\\2^{3}\\3^{3}\\4^{3}\end{pmatrix}}=C_{1}^{n}+7C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}}$

${\displaystyle p(k)=k^{3},\Delta p(k)=3k^{2}+3k+1,\Delta ^{2}p(k)=3(2k+1)+3=6k+6,\Delta ^{3}p(k)=6,\sum _{k=1}^{n}k^{3}=C_{1}^{n}+7C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}}$

${\displaystyle \sum _{i=1}^{n}i^{4}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}&C_{5}^{n}\end{pmatrix}}{\begin{pmatrix}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{pmatrix}}{\begin{pmatrix}1^{4}\\2^{4}\\3^{4}\\4^{4}\\5^{4}\end{pmatrix}}=C_{1}^{n}+15C_{2}^{n}+50C_{3}^{n}+60C_{4}^{n}+24C_{5}^{n}}$

${\displaystyle \sum _{i=1}^{n}i^{5}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}&C_{5}^{n}&C_{6}^{n}\end{pmatrix}}{\begin{pmatrix}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{pmatrix}}{\begin{pmatrix}1^{5}\\2^{5}\\3^{5}\\4^{5}\\5^{5}\\6^{5}\end{pmatrix}}=C_{1}^{n}+31C_{2}^{n}+180C_{3}^{n}+390C_{4}^{n}+360C_{5}^{n}+120C_{6}^{n}}$

${\displaystyle \sum _{i=1}^{n}(2i-1)^{2}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0\\-1&1&0\\1&-2&1\end{pmatrix}}{\begin{pmatrix}1^{2}\\3^{2}\\5^{2}\end{pmatrix}}=C_{1}^{n}+8C_{2}^{n}+8C_{3}^{n}}$

${\displaystyle \sum _{i=1}^{n}(3i-2)^{3}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}1^{3}\\4^{3}\\7^{3}\\10^{3}\end{pmatrix}}=C_{1}^{n}+63C_{2}^{n}+216C_{3}^{n}+162C_{4}^{n}}$

${\displaystyle \sum _{i=1}^{n}\left(i^{3}+2i+1\right)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}4\\13\\34\\73\end{pmatrix}}=4C_{1}^{n}+9C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}}$

## 范德蒙恒等式

${\displaystyle \sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}=C_{n}^{a+b}}$

 证明范德蒙恒等式 甲班有a個同學，乙班有b個同學，從兩個班中選出n名有${\displaystyle C_{n}^{a+b}}$種方法。 從甲班選k名，從乙班選n-k名有${\displaystyle C_{k}^{a}C_{n-k}^{b}}$種方法，考慮所有情況k=0,1,...,n，從兩個班中選出n名有${\displaystyle \sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}}$種方法。[6]

## 參考資料

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).