99
$\begingroup$

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.

$\endgroup$
2
  • 16
    $\begingroup$ 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. $\endgroup$ Commented May 9, 2011 at 16:15
  • 3
    $\begingroup$ See here for another combinatorial proof. $\endgroup$ Commented Apr 8, 2015 at 15:30

4 Answers 4

57
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ Here is the Sved article; I can't seem to find an electronic version of Kleitman's. $\endgroup$ Commented May 9, 2011 at 13:01
  • 8
    $\begingroup$ 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. $\endgroup$ Commented May 9, 2011 at 15:13
  • 3
    $\begingroup$ Links: jstor.org/stable/27642007 and jstor.org/stable/10.4169/amer.math.monthly.118.02.175 $\endgroup$ Commented May 9, 2011 at 15:18
  • 1
    $\begingroup$ @Hand Lundmark: The product should be a sum. Thanks to all for the references. $\endgroup$
    – Phira
    Commented May 9, 2011 at 15:20
  • 1
    $\begingroup$ The hard part of the proof is hidden in part (3) with the words "can be proved". Scott's answer here tries to actually prove this part with a giant lemma, but it doesn't look correct. The Sved article (second one here) gives a bijection due to Gessel but the description is slightly confusing: in the (c)-to-(b) move, when it refers to "the segment following it", this is referring to the entire path after the first contact point. (Took me a while to figure that out!) $\endgroup$
    – Matt
    Commented Dec 14, 2011 at 8:43
22
$\begingroup$

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 excess of the number 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 of subwords $AB$ has no effect on these operations (in particular the operations will never change such subwords), and that what remains when recursively removing such subwords is a word 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.

$\endgroup$
2
  • 1
    $\begingroup$ Instead of "subwords in the Dyck language for $\left\{A,B\right\}$", can't you just say "subwords of the form $AB$"? $\endgroup$ Commented Feb 10, 2015 at 19:20
  • 2
    $\begingroup$ I would also define what you mean by "majority of its letters $B$ over its letters $A$" (you seem to use it for "number of its letters $B$ minus number of its letters $A$", but it also could be mistaken for a ratio by someone not used to combinatorics). Otherwise, this is a very nicely written half-page introduction into crystal operators; I didn't expect to see a bijective proof of this identity that short! $\endgroup$ Commented Feb 10, 2015 at 19:27
21
$\begingroup$

There is also a probabilistic proof of this identity.

Start with an urn containing one red marble and one blue marble. Make a series of $n$ draws from the urn; for each draw, remove a random ball in the urn, then put it back, along with two extra balls of the same color. We then ask, what is the probability that exactly $k$ of the draws were red?

The probability that the first $k$ draws are red and the last $n-k$ are blue is $$ \frac12\cdot\frac{3}4\cdot\frac5{6}\cdots\cdot\frac{2k-1}{2k}\cdot\frac1{2k+2}\cdot\frac{3}{2k+4}\cdots\frac{2(n-k)-1}{2n}=\frac{(2k-1)!!(2(n-k)-1)!!}{(2n)!!} $$ where $n!!=\prod_{k=0}^{\lfloor n/2\rfloor-1}(n-2k)=n(n-2)(n-4)\cdots$.

It is not hard to see that every sequence of $k$ red and $n-k$ blue draws has this same probability; rearranging the order of draws just changes the order of the factors in the numerator. Therefore, the probability of $k$ red draws is, using the identities $(2n)!!=2^nn!$ and $(2k-1)!!=\frac{(2k)!}{(2k)!!}=\frac{(2k)!}{2^kk!}$, $$ \binom{n}k\frac{(2k-1)!!(2(n-k)-1)!!}{(2n)!!}=\frac{\binom{2k}k\binom{2(n-k)}{n-k}}{2^{2n}} $$ Since these probabilities must sum to $1$, the desired identity follows!

$\endgroup$
0
5
$\begingroup$

Here is another proof by Egecioglu. It was published as a technical report, not a journal paper, so it's not easy to find.

Update: The link to the technical report appears to be broken, so here is a subsequent paper by the same author containing that bijection.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .