# Proof sought for a sum involving binomials that simplifies to 1/2

A proof of:

\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*}

Conjecture based on the following Maple code:

Q := (1/2)^(2*m+1) * sum( binomial(m, k) * sum(binomial(m+1, j), j = 0 .. k), k = 0 .. m):
simplify([seq(Q, m = 1 .. 20, 1)]);

[1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2]

• Can you get it from binomial expansion of $(1+1)^m = 2^m$?
– oks
Commented Jan 31, 2014 at 15:32
• @oks, looks like you were onto something, but I really needed the breakdown Nick provided, ;-) Commented Jan 31, 2014 at 15:56

Since ${a\choose b} = {a\choose a-b}$, we have \begin{align*} \sum_{k = 0}^m{m\choose k}\sum_{j = 0}^k{m+1\choose j} &= \sum_{k = 0}^m{m\choose m-k}\sum_{j = 0}^k{m+1\choose m+1-j} \\ & = \sum_{r = 0}^m{m\choose r} \sum_{s = r+1}^{m+1}{m+1\choose s} \end{align*} where the last line follows by putting $r = m-k$ and $s = m+1-j$. If you add both sides together you get $2^{2m+1} = 2\times 2^{2m}$, so your result is true.

• Thanks Nick. Funny that, I had got the lhs from the rhs, thinking it was somewhat simpler, but didn't add them together. Actually, can you clarify what it is you are adding together: the lhs and the bottom line of the rhs? How do you get the powers of 2 by adding up? Sorry, I'm not familiar with this stuff. Thanks! Commented Jan 31, 2014 at 15:45
• Sure: Yes, I am adding together the LHS and the final expression on the second line. By reindexing the last sum (replacing $r$ with $k$ and $s$ with $j$) you get $$\sum_{k = 0}^m{m\choose k}\sum_{j = 0}^k {m+1\choose j}+\sum_{k = 0}^m{m\choose k}\sum_{j = k+1}^{m+1}{m+1\choose j} = \sum_{k = 0}^m{m\choose k}\sum_{j = 0}^{m+1}{m+1\choose j} = (1+1)^m(1+1)^{m+1}.$$ Commented Jan 31, 2014 at 15:48
• Got it, thanks Nick! :-) Commented Jan 31, 2014 at 15:53
• @PatrickT That's a really nice writeup! (Though you give me too much credit!) Commented Feb 1, 2014 at 5:28
• thanks: it feels a little long for what is a simple question with simple answer! The double change of indices is really clever: it took me a whole hour to fully understand its mechanics after you posted your answer. Credit is yours. Cheers Nick. Commented Feb 1, 2014 at 7:49

Suppose we seek to verify that $$\sum_{k=0}^m {m\choose k} \sum_{j=0}^k {m+1\choose j} = 2^{2m}.$$

We use the integral $${m+1\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{j+1}} \; dz.$$

This yields for the inner sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \sum_{j=0}^k \frac{1}{z^j}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \frac{1/z^{k+1}-1}{1/z-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{m+1} \frac{1/z^{k+1}-1}{1-z}\; dz.$$

Now the second term in the difference does not have a pole at zero so we are left with $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{k+1}} \frac{1}{1-z} \; dz.$$

This yields for the remaining sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \frac{1}{1-z} \sum_{k=0}^m {m\choose k} \frac{1}{z^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \frac{1}{1-z} \left(1+\frac{1}{z}\right)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+1}}{z^{m+1}} \frac{1}{1-z} \; dz.$$

Extracting the residue we find $$\sum_{q=0}^m {2m+1\choose q} = \frac{1}{2} \times 2^{2m+1} = 2^{2m},$$

as claimed.