交错组合求和

tommywong

求证或反证

$\displaystyle \sum_{k=0}^n (-1)^{n-k} C_n^k (x+k)^n=n!$

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

tommywong

$C_n^k C_k^m=C_n^m C_{n-m}^{k-m}$

$\displaystyle \sum_{k=m}^n (-1)^{n-k} C_n^k C_k^m=C_n^m \sum_{k=m}^n (-1)^{n-k} C_{n-m}^{k-m}$

当n-m≧1时，$\displaystyle \sum_{k=m}^n (-1)^{n-k} C_{n-m}^{k-m}=\sum_{k=0}^{n-m} (-1)^{n-m-k} C_{n-m}^k=(1-1)^{n-m}=0$

设$\displaystyle k^m=\sum_{j=0}^m a_j C_k^j$

$\displaystyle \sum_{k=0}^n (-1)^{n-k} C_n^k k^m=\sum_{j=0}^m a_j \sum_{k=j}^n (-1)^{n-k} C_n^k C_k^j=0$

展开$(x+k)^n$，m取n,n-1,...,0小于n+1，全部得0

tommywong

$\displaystyle \sum_{k=0}^n (-1)^{n-k} C_n^k (x+k)^n=\sum_{k=0}^n (-1)^{n-k} C_n^k k^n=n!\sum_{k=0}^n (-1)^{n-k} C_n^k C_k^n$

$\displaystyle=n! C_n^n \sum_{k=0}^n (-1)^{n-k} C_n^k C_0^k=n!$

tommywong

$\displaystyle k^{n+1}=(n+1)!C_k^{n+1}+\frac{n(n+1)}{2}k^n+...$

$\displaystyle \sum_{k=0}^n (-1)^{n-k} C_n^k k^{n+1}=\frac{n(n+1)}{2}\sum_{k=0}^n (-1)^{n-k} C_n^k k^n=\frac{n(n+1)!}{2}$

回到问题来源

$\displaystyle \sum_{i=1}^{n} i^{1} = C_n^1+C_n^2 $
$\displaystyle \sum_{i=1}^{n} i^{2} = C_n^1+3C_n^2+2C_n^3 $
$\displaystyle \sum_{i=1}^{n} i^{3} = C_n^1+7C_n^2+12C_n^3+6C_n^4 $
$\displaystyle \sum_{i=1}^{n} i^{4} = C_n^1+15C_n^2+50C_n^3+60C_n^4+24C_n^5 $
$\displaystyle \sum_{i=1}^{n} i^{5} = C_n^1+31C_n^2+180C_n^3+390C_n^4+360C_n^5+120C_n^6 $

现在证明了最后两项是$\displaystyle \frac{(m+1)!}{2},m!$

tommywong

$\displaystyle \sum_{k=0}^n (-1)^{n-k} C_n^k k^{n+2}=\frac{n(3n+1)(n+2)!}{24}$

后三项是$\displaystyle \frac{(3m-2)(m+1)!}{24}$

战巡

回复 1# tommywong


作为一个看到和号就讨厌的人，表示应该想办法把和号弄掉.......
令函数：
\[f(x,y)=e^{xy}(e^y-1)^{n}\]
易证
\[f(x,y)=\sum_{k=0}^n (-1)^{n-k}C^k_ne^{(x+k)y}\]
那么有
\[\frac{\partial^n f(x,y)}{\partial y^n}|_{y=0}=\sum_{k=0}^n (-1)^{n-k}C_n^k(x+k)^n\]
如果对$f(x,y)$中的$y$进行马克劳林展开，则有
\[f(x,y)=a_0(x)+a_1(x)y+a_2(x)y^2+...，a_i(x)=\frac{\frac{\partial^i f(x,y)}{\partial y^i}|_{y=0}}{i!}\]
因此原式相当于$a_n(x)·n!$
考虑到如下极限：
\[\lim_{y\rightarrow 0}\frac{f(x,y)}{y^n}=\lim_{y\rightarrow 0}\frac{e^{xy}(e^y-1)^{n}}{y^n}=1\]
可知马克劳林展开式中
\[f(x,y)=y^n+o(y^n)\]
即$0\le i<n$时，$a_i(x)=0$，且$a_n(x)=1$
因此原式等于$n!$
第二条就等价于求$a_{n-1}(x)(n-1)!$，前面已经证明了$a_{n-1}(x)=0$

战巡

回复 4# tommywong


表示自从开发了母函数法以后，这种乱七八糟的组合办法已经废弃了
令函数
\[f(x)=\sum_{i=0}^n e^{ix}=\frac{e^{(n+1)x}-1}{e^x-1}\]
则有
\[\frac{d^kf(x)}{dx^k}=\sum_{i=0}^n i^ke^{ix}\]
因此
\[\sum_{i=0}^n i^k=f^{(k)}(0)\]

tommywong

似乎又看不出规律了，
没有规律的话就比不上两个矩阵相乘的速度

$\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0\\
-1 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & -2 & 1 & 0 & 0 & 0 & 0\\
-1 & 3 & -3 & 1 & 0 & 0 & 0\\
1 & -4 & 6 & -4 & 1 & 0 & 0\\
-1 & 5 & -10 & 10 & -5 & 1 & 0\\
1 & -6 & 15 & -20 & 15 & -6 & 1
\end{pmatrix}
\begin{pmatrix}
1^6\\
2^6\\
3^6\\
4^6\\
5^6\\
6^6\\
7^6
\end{pmatrix}=
\begin{pmatrix}
1\\
63\\
602\\
2100\\
3360\\
2520\\
720
\end{pmatrix}
$

$C_n^1+63C_n^2+602C_n^3+2100C_n^4+3360C_n^5+2520C_n^6+720C_n^7$

tommywong

回复 6# 战巡

$\displaystyle \lim_{y\to 0} \frac{e^{xy}(1-e^y)^n}{y^n}=1$
怎么来的？

战巡

回复 9# tommywong


原式是$(e^y-1)^n$，你把它反过来当然就乱了......

反正这个不难证明，罗比达也好，泰勒展开也好，易证$e^y-1$与$y$等价无穷小

tommywong

我抄错了

这两个怎么求？

$\sum_{k=0}^n (-1)^{n-k} C_n^k (x+k)^{n+1},\sum_{k=0}^n (-1)^{n-k} C_n^k (x+k)^{n+2}$

$\sum_{k=0}^n (-1)^{n-k} C_n^k (x+k)^{n+m}$有通解吗？

战巡

回复 11# tommywong


这两个可以从上面那个式子继续求下去，相当于求$a_{n+1}(x)(n+1)!$和$a_{n+2}(x)(n+2)!$

前面已知：
\[f(x,y)=y^n+a_{n+1}(x)y^{n+1}+a_{n+2}(x)y^{n+2}+...\]
\[\frac{f(x,y)}{y^n}=1+a_{n+1}(x)y+a_{n+2}(x)y^{2}+...\]
因此
\[\frac{d\frac{f(x,y)}{y^n}}{dy}|_{y=0}=a_{n+1}(x)\]
\[a_{n+1}(x)=\lim_{y\rightarrow 0}\frac{e^{xy}(e^y-1)^{n-1}[n+e^yn(y-1)+(e^y-1)xy]}{y^{n+1}}=\frac{n}{2}+x\]
有：
\[\sum_{k=0}^n(-1)^{n-k}C^k_n(x+k)^{n+1}=a_{n+1}(x)(n+1)!=(\frac{n}{2}+x)(n+1)!\]

如果令$g(y)=\frac{e^y-1}{y}$，有$f(x,y)=e^{xy}g(y)^n$
\[\frac{\partial^2 f(x,y)}{\partial y^2}=e^{xy}g(y)^{n-2}[x^2g(y)^2+n(n-1)g'(y)^2+ng(y)(2xg'(y)+g''(y))]\]
易证$g(y)=1+\frac{y}{2}+\frac{y^2}{6}+...$，$g^{(m)}(0)=\frac{1}{m+1}$
因此：
\[2!·a_{n+2}(x)=\frac{\partial^2 f(x,y)}{\partial y^2}|_{y=0}=x^2+\frac{n(n-1)}{4}+nx+\frac{n}{3}\]
\[\sum_{k=0}^n(-1)^{n-k}C^k_n(x+k)^{n+2}=a_{n+2}(x)(n+2)!=\frac{12x^2+12nx+3n^2+n}{24}(n+2)!\]

通项就复杂咯，如果你有办法解决$\frac{d^mg(y)^n}{dy^m}$通项的话，倒是可以考虑用莱布尼兹公式弄出来