# proving inequality for combinatorial sum

If somone can prove the following for every $d\leq r$ (for $d=0,1$ its easy, see below, the case d=r may be also simple, I didn't find something helpful)

$$\frac{(d!)^2}{2^{n-2d}}\sum_{k=0}^{n}{n \choose k}{k+r \choose d}{n-k+r \choose d}\geq (n+2r)(n+2r-1)\ldots(n+2r-2d+1)$$

Moreover, if you can give an exact expression to the left sum, that will be great. thanks

for $d=1$ we get $\frac{4}{2^n}\cdot {\displaystyle\sum_{k=0}^{n}(k+r)(n-k+r){n \choose k}} = \frac{1}{2^{n-2}}\cdot {\displaystyle\sum_{k=0}^{n}{n \choose k}(nk-k^2+nr+r^2)} = \frac{1}{2^{n-2}}\cdot(n^22^{n-1}-n(n+1)2^{n-2}+2^n(nr+r^2)) = n^2+4nr-n+4r^2=(n+2r)(n+2r-1)+2r$

update 26/6: I have proved it (checked), it will be published as part of my paper, I'll add a link. If anyone will be interested I can write the idea and combinatorial intuition

-
A comment which is probably ultimately unhelpful: the series $\sum_{n=0}^\infty \binom{n+r}d x^n/n!$ equals $\binom rd {}_1F_1(r+1;r-d+1;x)$ (hypergeometric function). This means your sum $\sum_{k=0}^{n}{n \choose k}{k+r \choose d}{n-k+r \choose d}$ is equal to $n!$ times the coefficient of $x^n$ in the series (at $x=0$) for $\big(\binom rd {}_1F_1(r+1;r-d+1;x)\big)^2$. – Greg Martin May 29 '13 at 23:33