26
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Could you give the full reference to the paper where you found it? $\endgroup$ Apr 13, 2010 at 21:16
  • 1
    $\begingroup$ @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 $\endgroup$
    – j.c.
    Apr 13, 2010 at 22:24
  • $\begingroup$ @Nate: jc have told you that. $\endgroup$
    – Sunni
    Apr 14, 2010 at 0:59
  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Apr 15, 2010 at 2:37

2 Answers 2

6
$\begingroup$

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?

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

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.

$\endgroup$
5
  • $\begingroup$ As a non-layman, I'm curious: what do you have in mind in terms of the Haar measure on G(n,1)? $\endgroup$ Apr 14, 2010 at 18:34
  • 2
    $\begingroup$ I think that OP wanted a "counting in two ways"-proof of the equality, and not just a interpretation of LHS. (Did you?) $\endgroup$ Apr 14, 2010 at 18:54
  • $\begingroup$ @ Jakobsen: That is true. Dyer's explanation is insufficient. Also, I don'y know whether we shall introduce Haar measure to this problem. $\endgroup$
    – Sunni
    Apr 14, 2010 at 19:00
  • $\begingroup$ 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. $\endgroup$
    – Jason Dyer
    Apr 14, 2010 at 19:13
  • $\begingroup$ @miwalin: I'll think about it more then, and edit if a proof comes to me. $\endgroup$
    – Jason Dyer
    Apr 14, 2010 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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