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.

It's not difficult to show that

$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$

On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing terms gives us

$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}2^{-2n}=1$$

that is,

$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$$

My question: is there a more direct, combinatorial proof of this identity? I've been racking my brains trying to come up with one but I'm not having much success.

share|improve this question
5  
This is identity 5.39 (p. 187, 2nd ed.) in Concrete Mathematics. The proof they give there uses Vandermonde's convolution and the identity $\binom{-1/2}{n} = (-1/4)^n \binom{2n}{n}$. It's not a combinatorial proof, but it might be interesting to take a look at anyway. –  Mike Spivey May 9 '11 at 16:15
add comment

2 Answers

up vote 24 down vote accepted

It is possible to give a direct combinatorial proof, but it is quite difficult to find it.

One possibility is to use paths between points with integer coordinates and steps $(1,1)$ and $(1,-1)$.

1) $\binom{2n}{n}$ counts all paths from $(0,0)$ to $(2n,0)$.

2) $2^{2n}$ counts all paths starting from $(0,0)$ with $2n$ steps.

3) $\binom{2n}{n}$ counts all paths with $2n$ steps that never touch the $x$-axis again after the start. (This one is not obvious, but can be proved with a bijection.)

Now you can conclude that all paths are a concatenation of a path that returns a certain number of times to the $x$-axis and a path that never does.

Note that the main difficulty here was that the two binomial coefficients are interpreted differently.

Edited to add reference: In Richard P. Stanley: Enumerative Combinatorics Volume 1, Chapter 1, Solution to exercice 2c the following reference is given:

The problem of giving a combinatorial proof was raised by P. Veress and solved by G. Hajos in the 1930s. A recent proof appears in D.J. Kleitman, Studies in Applied Math. 54 (1975), 289 - 292. See also M. Sved, Math. Intelligencer, vol.6, no. 4 (1984), 44-45.

But I have not looked to check which article gives the proof I have outlined above.

share|improve this answer
1  
Here is the Sved article; I can't seem to find an electronic version of Kleitman's. –  J. M. May 9 '11 at 13:01
4  
There's also another combinatorial proof by de Angelis in Amer. Math. Montly, Aug-Sept 2006, and a probabilistic proof, which generalizes to $\prod_{i_1+\dots+i_m=n} \binom{2i_1}{i_1} \dots \binom{2i_m}{i_m} = (4^n/n!) \cdot \Gamma(m/2+n) / \Gamma(m/2)$, by Chang & Xu in Amer. Math. Montly, Feb 2011. –  Hans Lundmark May 9 '11 at 15:13
1  
    
@Hand Lundmark: The product should be a sum. Thanks to all for the references. –  Phira May 9 '11 at 15:20
    
Oops! Of course it was meant to be a sum. Nice answer, by the way (even though it made me waste way too much time today trying to figure out what that bijection is...). –  Hans Lundmark May 9 '11 at 17:35
show 4 more comments

Here is another proof, one that I slightly prefer. I'll start with the hardest part.

Lemma. The number of all words of length $n$ in the alphabet $\{A,B\}$ such that no prefix (left factor) of it contains more letters $B$ than $A$, is $\binom n{\lceil n/2\rceil}$.

Instead of these words one may also take, interpreting $A$ as an up-step and $B$ as a down-step, paths as in the answer by Phira that never go below the horizontal axis; or one can formulate as ballot sequences as in Bertand's ballot problem, with the difference that we allow $B$ to catch up with $A$ without overtaking, and that the (non-negative) size of the eventual lead of $A$ is not fixed.

Proof. The following step can be applied to any word for which some prefix does contain more letters $B$ than$~A$: find the smallest prefix for which the majority of its letters $B$ over its letters $A$ is maximal among all prefixes, and change its last letter (which is a $B$) into $A$. There is an inverse step that can be applied to any word with more letters $A$ than letters $B$ (or more generally to a word for which some suffix (right factor) has this property): find the smallest suffix for which the majority of its letters $A$ over its letters $B$ is maximal among all suffixes, and change its first letter (which is an $A$) into $B$. The easiest way to see that these are inverse operations is that the presence subwords in the Dyck language for $\{A,B\}$ has no effect on these operations (in particular they will never change inside such words), and that what remains when ignoring such subwords is of the form $BB\ldots BAA\ldots A$, where the last $B$ respectively first $A$ will be changed. Now given a word of length $n$ with $\lceil n/2\rceil$ letters $A$ and $\lfloor n/2\rfloor$ letters $B$, one can iterate the first operation until no prefix contains more letters $B$ than $A$, and conversely given a word of length $n$ satisfying that condition, if there are $d\geq0$ more letters $A$ than $B$ in all, one can iterate the reverse operation $\lfloor d/2\rfloor$ times to obtain a word of length $n$ with $\lceil n/2\rceil$ letters $A$ and $\lfloor n/2\rfloor$ letters $B$. This bijection proves the lemma. QED

Now to prove the identity of the question, consider the words of length $2n+1$ in which the letters $A$ are in the majority; their number is $2^{2n+1}/2=2^{2n}$. Consider the longest prefix (possibly empty) in which there are as many letters $A$ as $B$; it has an even length $2k$, and given that length there are $\binom{2k}k$ possibilities for this prefix. The next letter is necessarily an $A$, and after that there is a suffix of length $2n-2k$ in which no prefix (of that suffix) contains more letters $B$ than $A$. By the lemma there are $\binom{2n-2k}{n-k}$ of them, whence the result.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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