Finding a closed form expression for this sum For non-negative $n$, find
$$
\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}.
$$
I can't figure this out. Any ideas?
 A: The sum is a convolution of the sequence $a_n = \binom{2n}{n}$ with itself. This suggests generating functions. Multiplying generating functions for two sequences results in a generating function for the convolution of the two sequences:
If $f(x) = \sum_{n \geq 0} a_n x^n$ and $g(x) = \sum_{n \geq 0} b_n x^n$, then $$f(x)g(x) = \sum_{n \geq 0} \left(\sum_{k=0}^n a_k b_{n-k}\right) x^n$$
The generating function $f$ for the sequence $\binom{2n}{n}$ is given by $$f(x) = \frac{1}{\sqrt{1 - 4x}}$$
Since $[f(x)]^2 = \frac{1}{1-4x}$, which is the generating function for $4^n$, the given sum is $4^n$. 
There are approaches that don't involve generating functions, but the generating function calculation is very quick. 
A: The sum has the form $d_n = \sum_{k=0}^n c_k c_{n-k}$, where $c_k = \binom{2k}{k}$. The sum is known as the Cauchy product. The generating function for $d_n$ is the second power of the generating function of $c_n$.
$$
  \sum_{n=0}^\infty d_n x^n = \left( \sum_{k=0}^\infty c_k x^k \right)^2 = \left( \frac{1}{\sqrt{1-4x}} \right)^2 = \frac{1}{1-4x} = \sum_{k=0}^\infty 2^{2k} x^k
$$
Thus
$$
   \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 2^{2n}
$$
