Closed form solution and combinatorial proof.

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.

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

$$\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.

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

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.