4
$\begingroup$

Recently, I came across the following exercise on the course of discrete math

Find a closed form for $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$

So I tried some of the usual techniques: Let $f(x)=\sum_{k=0}^n\binom{2n}{k}x^k$.
If we denote $F(x)=\frac16x^3\left(xf'(x)\right)'''$ then $F(x)=\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}x^k$, so the desired sum is $F(1)$.
Problem here is that I can't find a closed expression for $f(x)$. Clearly, $(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k$, but how can I take out only the first 'half' of the terms?

Second thing I tried was to take $g(x)=(1+x)^{2n}$ and then denote $G(x)=\frac16x^3\left(xg'(x)\right)'''$.
Then $G(x)=\sum_{k=0}^{2n}k\binom{k}{3}\binom{2n}{k}x^k$. So, if we look at $$h(x)=G(x)\frac1{1-x}=\sum_{j=0}^\infty\left(\sum_{k=0}^jk\binom{k}{3}\binom{2n}{k}\right)x^j$$ So the desired sum will be the coefficient of $x^n$. But here it doesn't work either, as
$$h(x)=\binom{2n}{3}(2nx+3)\frac{(1+x)^{2n-4}}{1-x}$$ But I can't find a closed form for the coefficient of $x^n$.

Any help will be much appreciated.

$\endgroup$
5
$\begingroup$

$$\sum_{k=0}^{n} k{k\choose 3}{2n\choose k}\\ =\sum_{k=0}^{n}\frac{k( k!)(2n)!}{(k-3)!3!k!(2n-k)!}\\ ={2n\choose 3}\sum_{k=0}^{n}\frac{k(2n-3)!}{(k-3)!(2n-k)!}\\ ={2n\choose 3}\sum_{k=0}^{n}k{2n-3\choose k-3}\\ ={2n\choose 3}\sum_{h=0}^{n-3}(h+3){2n-3\choose h}\\ ={2n\choose 3}\sum_{h=0}^{n-3}\left[(2n-3){2n-4\choose h-1}+3{2n-3\choose h}\right]\\ ={2n\choose 3}\left[(2n-3)\left(2^{2n-5}-{2n-4\choose n-2}/2-{2n-4\choose n-3}\right)\\ +3(2^{2n-4}-{2n-3\choose n-2})\right]$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you get the last equality? $\endgroup$ – Dennis Gulko Jul 5 '14 at 8:21
  • 2
    $\begingroup$ He is exploting the facts that $$\sum_{h=0}^{n}\binom{2n+1}{h}=2^{2n},\quad \sum_{h=0}^{n}\binom{2n+2}{h}=\frac{2^{2n+2}-\binom{2n+2}{n+1}}{2}.$$ $\endgroup$ – Jack D'Aurizio Jul 5 '14 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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