2
$\begingroup$

First of all, I would like to figure out a closed form solution for the following summation:

$$\sum^{n}_{k=0} C(n,k)\cdot C(2n,n+k)$$

Where C(n,k) means n choose k, or $\frac{n!}{(n-k)!\cdot k!}$

And also demonstrate that this and the closed form solution are equal through a combinatorial proof.

I started by rewriting it into:

$$\sum^{n}_{k=0} C(n,n-k) \cdot C(2n,n-k)$$

But I am not sure if this is actually more helpful, and I am quite stuck.

$\endgroup$
  • $\begingroup$ It's been fixed now, thank you! It was multiplication $\endgroup$ – Blessoul Jan 12 '15 at 21:34
  • $\begingroup$ This is simply ${\large C}_{3n}^n$. $\endgroup$ – Lucian Jan 12 '15 at 21:54
2
$\begingroup$

$$\sum_{k=0}^n\binom{n}k\binom{2n}{n+k}=\sum_{k=0}^n\binom{n}k\binom{2n}{n-k}=\binom{3n}n$$

by Vandermonde’s identity. The link gives a combinatorial proof of Vandermonde’s identity, which you can easily specialize to this particular case of it.

$\endgroup$
  • $\begingroup$ Sweet! Thanks! Accepted. $\endgroup$ – Blessoul Jan 12 '15 at 22:05
  • $\begingroup$ @Blessoul: You’re welcome! $\endgroup$ – Brian M. Scott Jan 12 '15 at 22:09
0
$\begingroup$

This one can also be done using complex variables.

Suppose we seek to evaluate $$\sum_{k=0}^n {n\choose k} {2n\choose n+k}.$$

Introduce the integral representation $${2n\choose n+k} =\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+k+1}} \; dz.$$

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sum_{k=0}^n {n\choose k} \frac{1}{z^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \left(1+\frac{1}{z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{2n+1}} \left(z+1\right)^n \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{3n}}{z^{2n+1}} \; dz.$$

This evaluates to $${3n\choose 2n} = {3n\choose n}$$ by inspection.

$\endgroup$

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.