Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.