Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

As promised, here is the solution as part of my work (joint with Amnon Ta-Shma) on the Benes network


section 5

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.