uyhip2016 November

题目

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

题意：求 $$\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.”

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