# Algebraic proof of combinatorial identity

I would like to obtain the algebraic proof for the following identity. I already know the combinatorial proof but the algebraic proof is evading me.

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

Thanks.

-

We make use of the Binomial Theorem. Observe that: \begin{align*} \sum_{k=0}^{3n} \binom{3n}{k}x^k &= (1+x)^{3n} \\ &= (1+x)^n(1+x)^{2n} \\ &= \left[ \sum_{i=0}^{n} \binom{n}{i}x^i \right] \left[ \sum_{j=0}^{2n} \binom{2n}{j}x^j \right] \\ &= \sum_{k=0}^{3n} \left[\sum_{r=0}^n\binom{n}{r}\binom{2n}{k-r}\right]x^k \\ \end{align*}

Hence, by setting $k=n$, we compare the coefficients of $x^n$ of both sides to obtain: $$\binom{3n}{n} = \sum_{r=0}^n\binom{n}{r}\binom{2n}{n-r}$$ as desired.

-
Good. The i in the last x^i term in line 3 should be j. –  Anonymous Aug 30 '13 at 14:40
Also, how did you get from line 3 to line 4? (The lines with the complicated notation) –  Anonymous Aug 30 '13 at 14:41
Recall how we multiply polynomials together. That is, if $f(x) = \sum_{i=0}^M a_ix^i$ and if $g(x) = \sum_{j=0}^N b_jx^j$, then the degree of their product will be $M+N$ and the coefficient of each $x^k$ is obtained by summing over the products of the coefficients of $x^i$ and $x^j$ such that $i+j=k$. In other words: $$f(x)g(x) = \sum_{k=0}^{M+N} \left[ \sum_{r=0}^M a_rb_{k-r} \right]x^k$$ –  Adriano Aug 30 '13 at 16:49
Apologies for the typos. They've been fixed. –  Adriano Aug 30 '13 at 16:56

Hint

Calculate by two ways the coefficient of the term $x^n$ of $(1+x)^n(1+x)^{2n}$ .

-