uyhip2016 November

r_64 posted @ 2016年11月30日 22:18 in 未分类 with tags uyhip , 658 阅读

题目

听说,水题和手速狗更配哦。

题意:求$$\sum_{k=0}^n\binom{n}{k}\frac{(-1)^k}{k+j}$$

首先打表找规律(因为Michael说有closed-form,所以不虚),得到答案为$\frac{1}{j\binom{n+j}{j}}$

然后就是证明了。。数学归纳法xjb推推柿子就好。。对$n$归纳。

$n=0$时两边都是$\frac{1}{j}$,成立。

$n>0$时这么推(其实就是乱推。。然后居然推出来了)

\begin{eqnarray}
&&\sum_{k=0}^n\binom{n}{k}\frac{(-1)^k}{k+j}\nonumber\\
&=&\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{(-1)^k}{k+j}+\sum_{k=1}^n\binom{n-1}{k-1}\frac{(-1)^k}{k+j}\nonumber\\
&=&\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{(-1)^k}{k+j}+\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{(-1)^{k+1}}{k+j+1}\nonumber\\
&=&\frac{1}{j\binom{n-1+j}{j}}-\frac{1}{(j+1)\binom{n+j}{j+1}}\nonumber\\
&=&\frac{(j+1)\binom{n+j}{j+1}-j\binom{n-1+j}{j}}{j(j+1)\binom{n-1+j}{j}\binom{n+j}{j+1}}\nonumber\\
&=&\frac{\frac{n(n-1+j)!}{(n-1)!j!}}{j(j+1)\binom{n-1+j}{j}\binom{n+j}{j+1}}\nonumber\\
&=&\frac{n(n-1)!(j+1)!}{j(j+1)(n+j)!}\nonumber\\
&=&\frac{1}{j\binom{n+j}{j}}\nonumber
\end{eqnarray}

更多信息详见我交上去的答案


这个题确实很优美。说实话我刚看到柿子的时候我是不相信它有closed-form的,即使有也要用到调和级数之类的东西。用一堆组合数来表示一个组合数的倒数,发现这个公式的人真的很厉害。Michael Brand在题解中写道:

“The result is not just a cute riddle. It describes the reciprocal of a binomial in terms of a sum of binomial terms, which, in turn, is a powerful tool for solving series involving reciprocals of binomials, which Leibniz did.”

也许以后遇到组合数倒数相关的东西,能够想到这个柿子推一推?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter