Compute $\sum_{k=0}^n \binom{2n}{k} \binom{n}{k}$ using generating functions

Question

How do I compute $\sum_{k=0}^n \binom{2n}{k} \binom{n}{k}$ using generating functions? I'm trying to make a generalization for a competition math problem, namely this.

Answer 1

The trick is to use $\binom{n}{k}=\binom{n}{n-k}$. Our problem is the special case of Vandermonde's identity with $m=2n,\,r=n$, so the answer is $\binom{3n}{n}$. This algebraic proof uses coefficients in generating functions - to be precise, polynomials, i.e. generating functions with only finitely many nonzero coefficients. In particular, $\sum_{k=0}^n\binom{2n}{k}\binom{n}{n-k}=\binom{3n}{n}$ follows from evaluating the $x^n$ coefficient in $(1+x)^{2n}(1+x)^n=(1+x)^{3n}$.

Answer 2

Using the coefficient extractor thingy, Eg. \begin{eqnarray*} \binom{2n}{k} = [x^0]: \frac{(1+x)^{2n}}{x^k}. \end{eqnarray*} We have \begin{eqnarray*} \sum_{k=0}^{n} \binom{n}{k} \binom{2n}{k} &=& [x^0]: \sum_{k=0}^{n} \binom{n}{k} \frac{(1+x)^{2n}}{x^k} \\ &=& [x^0] : (1+x)^{2n} \left( 1+ \frac{1}{x} \right)^n \\ &=& [x^n] : (1+x)^{3n} = \color{red}{\binom{3n}{n}}. \end{eqnarray*}