# Is there a combinatorial interpretation of the identity $\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}$?

I came across the following combinatorial identity in a paper by Victor H. Moll and Dante V. Manna '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 a combinatorial interpretation 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

• Could you give the full reference to the paper where you found it? – Nate Eldredge Apr 13 '10 at 21:16
• @Nate: I bet it's this one: dx.doi.org/10.1016/j.exmath.2009.02.005 "A remarkable sequence of integers" by Victor H. Moll and Dante V. Manna. Expositiones Mathematicae Volume 27, Issue 4, 2009, Pages 289-312 – j.c. Apr 13 '10 at 22:24
• @Nate: jc have told you that. – Sunni Apr 14 '10 at 0:59
• You might want to check out "Proofs that Really Count" by Art Benjamin. It has a bunch of combinatorial proofs of identities and one whole chapter is on binomial coefficient identities. I don't know if this one is in there, but it might be a good place to look for general insight. – Aeryk Apr 15 '10 at 2:37

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