Finding a closed form expression for this sum [duplicate]

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?

-

marked as duplicate by robjohn♦Apr 13 '13 at 8:11

This is a well known example of an identity for which it is much easier to find a proof using generating functions than by a direct combinatorial argument. For the question of nonetheless giving a combinatorial argument, see math.stackexchange.com/q/37971 and its duplicate math.stackexchange.com/q/72367 – Marc van Leeuwen Apr 13 '13 at 5:31
@MarcvanLeeuwen: nicely researched. Both of these answers were outlined in the first question you cite. I will close this, but not merge since these answers don't answer the original. – robjohn Apr 13 '13 at 8:09
@MarcvanLeeuwen How did you search for that? I didn't know how to search for it because there's no specific name or term associated with it. O.w. I'd just have to look through all the results one at a time. – AlanH Apr 13 '13 at 20:21
Looking in my history, it appears that the fruitful search was on 'bijective proof Stanley' on this site. I knew this was an exercise in Stanley's EC1, but it was a bit of luck. I did change the title so as to contain 'central binomial' to help future searching. – Marc van Leeuwen Apr 13 '13 at 20:43

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}$$

-
How do you know that the 2nd term is equal to $(1/\sqrt{1-4x})^2$? – AlanH Apr 13 '13 at 20:32
@AlanH Because $\binom{2k}{k} = (-1)^k 4^k \binom{-1/2}{k}$ by using duplication formula, and thus $$\sum_{k=0}^\infty \binom{2k}{k} x^k = \sum_{k=0}^\infty (-4x)^k \binom{-1/2}{k} = \frac{1}{\sqrt{1-4x}}$$ where the last equality is the generalized binomial theorem in action. – Sasha Apr 14 '13 at 0:32

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.

-