Prove that $\sum_i {n\choose i}{2n\choose n-i}={3n\choose n}$.

combinatoricsgenerating-functions

I want to calculate Example 9 on page 130 of Herbert S. Wilf's book generatingfunctionology (2. edition)link to the pdf of the book via the Snake Oil method. I followed the suggestion given by the author to temporarily replace $2n$ by $m$ and $n-i$ by $r-i$ and I got the following generating function
\begin{align}
F(x)&=\sum_{n\geq 0}x^n\sum_i{n\choose i}{m\choose r-i}\nonumber\\
&=\sum_i{m\choose r-i}\sum_{n\geq 0}{n\choose i}x^n\nonumber\\
&=\sum_i{m\choose r-i}\frac{x^i}{(1-x)^{i+1}}\nonumber\\
&=\frac{x^r}{(1-x)^{r+1}}\sum_i{m\choose r-i}\left(\frac{1-x}{x}\right)^{r-i}\nonumber\\
&=\frac{x^r}{(1-x)^{r+1}}\left(1+\frac{1-x}{x}\right)^{m}\nonumber
\end{align}

The 3rd equality is obtained by the identity $(4.3.1)$ on page 120 of the book and the last equality is obtained by the binomial theorem. The Snake Oil method suggest to find the coefficients of this generating function because this is the answer we are looking for, but I don't know how to do this.

Note that I used the customary conventions about binomial coefficients and the ranges of summation variables given in the book. These are: first that the binomial coefficient ${x\choose m}$ vanishes if $m < 0$ or if $x$ is a nonnegative integer that is smaller than $m$. Second, a summation variable whose range is not
otherwise explicitly restricted is understood to be summed from $-\infty$ to $\infty$.

Best Answer

\begin{eqnarray*} \sum_{i=0}^{n} \binom{n}{i} \binom{2n}{n-i} &=& [x^n] \sum_{i=0}^{n} \binom{n}{i} x^{i} (1+x)^{2n} \\ &=& [x^n] (1+x)^n (1+x)^{2n} = [x^n]: (1+x)^{3n} = \binom{3n}{n}.\\ \end{eqnarray*}

Related Question