4
$\begingroup$

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]
Improve this question
$\endgroup$
  • $\begingroup$ Can you get it from binomial expansion of $(1+1)^m = 2^m$? $\endgroup$ – oks Jan 31 '14 at 15:32
  • $\begingroup$ @oks, looks like you were onto something, but I really needed the breakdown Nick provided, ;-) $\endgroup$ – PatrickT Jan 31 '14 at 15:56
5
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – PatrickT Jan 31 '14 at 15:45
  • 2
    $\begingroup$ 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}.$$ $\endgroup$ – Nick Strehlke Jan 31 '14 at 15:48
  • $\begingroup$ Got it, thanks Nick! :-) $\endgroup$ – PatrickT Jan 31 '14 at 15:53
  • $\begingroup$ FYI, this question was in the context of math.stackexchange.com/questions/657886/…. See also: patricktoche.com/public/CoinTossCompetition.pdf (this pdf will remain online for a little while) $\endgroup$ – PatrickT Jan 31 '14 at 21:54
  • $\begingroup$ @PatrickT That's a really nice writeup! (Though you give me too much credit!) $\endgroup$ – Nick Strehlke Feb 1 '14 at 5:28
1
$\begingroup$

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.

Improve this answer
$\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.