69
$\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$
  • 10
    $\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$ – Mike Spivey May 9 '11 at 16:15
  • 2
    $\begingroup$ See here for another combinatorial proof. $\endgroup$ – punctured dusk Apr 8 '15 at 15:30
43
$\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$
  • 2
    $\begingroup$ Here is the Sved article; I can't seem to find an electronic version of Kleitman's. $\endgroup$ – J. M. is a poor mathematician May 9 '11 at 13:01
  • 6
    $\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$ – Hans Lundmark May 9 '11 at 15:13
  • 2
    $\begingroup$ Links: jstor.org/stable/27642007 and jstor.org/stable/10.4169/amer.math.monthly.118.02.175 $\endgroup$ – Hans Lundmark May 9 '11 at 15:18
  • $\begingroup$ @Hand Lundmark: The product should be a sum. Thanks to all for the references. $\endgroup$ – Phira May 9 '11 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 Dec 14 '11 at 8:43
15
$\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 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 of 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.

$\endgroup$
  • $\begingroup$ Instead of "subwords in the Dyck language for $\left\{A,B\right\}$", can't you just say "subwords of the form $AB$"? $\endgroup$ – darij grinberg Feb 10 '15 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$ – darij grinberg Feb 10 '15 at 19:27
5
$\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$
2
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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