方幂和及其推广和式

tommywong

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

证明：$ \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}} $
$ m=\deg(p) $
$ p(k) $为m阶多项式，待定成组合数：

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

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

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

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

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

$ 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}} $
$ \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的值。

证明：$ \sum _{k=1}^{n}p(k)=\sum _{j=1}^{m+1}C_{j}^{n}\Delta ^{j-1}p(1) $
$ m=\deg(p),\Delta 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} $

$ \Delta C_{l}^{k}=C_{l}^{k+1}-C_{l}^{k}=C_{l-1}^{k} $

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

$ \Delta ^{j}p(1)=a_{j} $

$ p(k)=\sum _{j=0}^{m}C_{j}^{k-1}\Delta ^{j}p(1) $

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

例子：
$ \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} $

$ p(k)=k,\Delta p(k)=1 $
$ p(1)=1,\Delta p(1)=1,\sum _{k=1}^{n}k=C_{1}^{n}+C_{2}^{n} $
$ \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} $（等差数列求和）

$ p(k)=a+d(k-1),\Delta p(k)=d $
$ p(1)=a,\Delta p(1)=d,\sum _{k=1}^{n}[a+d(k-1)]=aC_{1}^{n}+dC_{2}^{n} $
$ \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} $

$ p(k)=k^{2},\Delta p(k)=2k+1,\Delta ^{2}p(k)=2 $
$ 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} $
$ \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} $

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

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

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

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

$ \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} $
《方幂和及其推广和式》：cnki.com.cn/Article/CJFDTOTAL-SXYG201607113.htm

Jan

有点晕……台湾教程

tommywong

回复 2# Jan

什么语言都会晕，这东西非常扯谈

这里战巡也弄了一个拉普拉斯变换方法
forum.php?mod=viewthread&tid=3758&highlight=

我在维基教科书也写了裂項法、錯位相減法、逐項求導、阿貝爾變換、朱世杰恒等式等方法

其妙

回复 3# tommywong
你还参与维科百基编写？