# What is the combinatorial intepretation to this identity?

I came across the following combinatorial identity in a paper 'a remarkable sequence of integers'.

$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}.$

I gave an elementary proof as follows, yet I a combinatorial intepretation seems difficult to a layman like me. So I post it here for discussion.

My elementary proof is through the method of coefficients.

Let $[t^n]f(t)$ be the coefficient of $t^n$ in $f(t)$.

Lemma: $[t^k]\frac{1}{\sqrt{1-t}}=4^{-k} \binom{2k}{k}$.

Proof:

\begin{aligned} [t^k]\frac{1}{\sqrt{1-t}} &=\binom{-1/2}{k} (-1)^k \\\\ &=\binom{1/2+k-1}{k} \\\\ &=\frac{(k-1/2)(k-3/2)\cdots (1/2)}{k!}\\\\ &=\frac{(2k-1)(2k-3)\cdots 1}{k!}2^{-k} \\\\ &=\frac{(2k)(2k-1)(2k-2)(2k-3)\cdots 2\cdot1}{k!\cdot k!} 4^{-k} \\\\ &= 4^{-k} \binom{2k}{k} \end{aligned}

QED

Moreover, it is easy to see

\begin{aligned} \binom{2m-k}{m}&=\binom{2m-k}{m-k} \\\\ &=\binom{-(2m-k)+m-k-1}{m-k}(-1)^{m-k}\\\\ &= \binom{-m-1}{m-k} (-1)^{m-k} \\\\ &=[t^{m-k}]\frac{1}{(1-t)^{m+1}} \end{aligned}

Proposition:

$$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m}= 4^{-m} \binom{4m+1}{2m}.$$

Proof:

\begin{aligned} \sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} &= [t^m]\left(\frac{1}{\sqrt{1-t}} \frac{1}{(1-t)^{m+1}}\right) \\\\ &= [t^m]\frac{1}{(1-t)^{m+(3/2)}} \\\\ &=\binom{-m-(3/2)}{m} (-1)^m \\\\ &=\binom{2m+(1/2)}{m} \\\\ &= 2^{-m} \frac{(4m+1)(2m-1)\cdots(2m+3)}{m!} \\\\ &=2^{-m} \frac{(4m+1)(2m-1)\cdots(2m+3)}{m!} \frac{4m(4m-2)\cdots(2m+2)}{4m(4m-2)\cdots(2m+2)} \\\\ &=2^{-2m}\frac{(4m+1)!}{(2m+1)!(2m)!} \\\\ &=2^{-2m} \binom{4m+1}{2m} \end{aligned}

QED

-
Oh my god. I just viewed the source. Is that really how you type LaTeX? The entire thing is a single line. –  Harry Gindi Apr 13 '10 at 14:16
OK, that's all the editing I'm going to do. I hope I haven't damaged your style too much. –  David Speyer Apr 13 '10 at 14:38
@David: nope, because LaTeX works by parsing and expanding catcodes, not by pattern matching. So the first backslash gets expanded first, capturing the second and leaving the k alone. A quick check confirms this. –  Loop Space Apr 13 '10 at 14:39
Also, I think that the 4^m in the first displayed equation should be 4^{-m}. I deliberately only fixed typesetting, not mathematics. –  David Speyer Apr 13 '10 at 14:43
Could you give the full reference to the paper where you found it? –  Nate Eldredge Apr 13 '10 at 21:16

I don't have an answer, but I have spend a couple of hours on it, so here is some of my thoughts on the problem.

In the following I will identify expressions with sets, so $2^n$ corresponds to the set of 01-sequences of length n, $\binom{n}{k}$ is the set of 01-sequence of length n with exactly k 1s, and products and sums corresponds to taking product sets and unions.

We want to find a bijective function from $\sum_{k=0}^m 2^{2(m-k)} \binom{2k}{k} \binom{2m-k}{m}$ to $\binom{4m+1}{2m}$ (I have multiplied with $4^m$ on both sides). Let me give an example a similar looking equality (you can skip the rest of this paragraph if you want): $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}=\binom{4m}{2m}$. Take an element in $\binom{4m}{2m}$, and pair the terms, so we have a sequence over {(00),(01),(10),(11)} of length $2m$. We have an even number of 1s in the sequence, so there must be an even number of pairs that contain exactly one 1, and thus and even number of pairs with (00) or (11). Let the number of (00) and (11) in the sequence of pairs be 2k. Now k of these must be (00) and k of them is (11) is the number of 0s and 1s are the same. The 2k terms in the 2m length sequence can be chosen in $\binom{2m}{2k}$ ways, the k (11)s of these 2k terms can chosen in $\binom{2k}{k}$ ways and in the rest of the $2m-2k$ terms we must choose between (10) and (01). This gives a factor $2^{2(m-k)}$, so we have a 1-1 correspondence between $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}$ and $\binom{4m}{2m}$.

An important part of such a proof is to find out what k represents. In your equality, it turns out that the k=0 part of the sum is about $\sqrt{\frac{1}{2}}$ of the whole sum. Do anyone know where the $\sqrt{\frac{1}{2}}$ could come from? One way to find out what k is, would be to find an injective function from the k=0 term, $2^{2m}\binom{2m}{m}$, to $\binom{4m+1}{2m}$ and see what the image set looks like. But I haven't been able to find such a function, that is, I cannot find a combinatorial proof that $2^{2m}\binom{2m}{m}\leq \binom{4m+1}{2m}$ (nor that $\binom{4m}{2m}<2^{2m}\binom{2m}{m}$). Perhaps you should try to ask this in you question?

-
Maybe it is easier to find something multiplying both sides with 1/(m+1), so you get odd Catalan numbers in total. –  Martin Rubey Apr 18 '10 at 12:26
The identity you prove is the same as the one appeared in <A remarkable sequence of integers> pp298. You may check that. –  Sunni Apr 18 '10 at 16:46

Since you describe yourself as a "layman" I'm guessing you don't want to hear about the Haar measure on Grassmannian space G(n,1), so here's my best intuitive explanation of the left hand side of the equation combinatorically:

Imagine you have a set of n families. Each family has either 1 or 2 children. The two-child families have an older and a younger child, so the children are distinguishable.

Exactly 1/2 of them must have exactly one boy. The remaining single-child families must have girls.

Of the two-child families, when counting up all the boys and girls together there must be an equal number of boys and girls. (It's possible for 0 families up to (1/2)n families to have two children.)

Without the $2^{-2k}$ term, the LHS enumerates the possible sets of families that follow the conditions above given $2m=n$.

With the $2^{-2k}$ term, there's an additional condition in enumerating: take the configurations that involve r two-child families, say there's c of them. Form the ratio between c and the total ways the genders of the two-child families could come out if it wasn't an equal number of boys and girls. The sum of all ratios for all values of r from 0 to (1/2)n achieves the LHS described in the equation.

-
As a non-layman, I'm curious: what do you have in mind in terms of the Haar measure on G(n,1)? –  Michael Lugo Apr 14 '10 at 18:34
I think that OP wanted a "counting in two ways"-proof of the equality, and not just a interpretation of LHS. (Did you?) –  Sune Jakobsen Apr 14 '10 at 18:54
@ Jakobsen: That is true. Dyer's explanation is insufficient. Also, I don'y know whether we shall introduce Haar measure to this problem. –  Sunni Apr 14 '10 at 19:00
Michael, regarding the Haar measure on G(n,1): take the reciprocal of the rational part of every 4th term (there's an offset but I don't know offhand, I think 2) and you get the sequence. –  Jason Dyer Apr 14 '10 at 19:13
@miwalin: I'll think about it more then, and edit if a proof comes to me. –  Jason Dyer Apr 14 '10 at 19:16