Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $m$ be a positive integer. I have trouble proving that $$\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$$ Anyone?

share|cite|improve this question

Generating functions! Multiply both sides of the desired identity by $x^m$, sum over all nonnegative integers $n$, and check that you get the same function on both sides.

First, note that your formula is valid for $m\ge1$; for $m=0$ the answer is $1/2$. In particular, making a generating function out of the right-hand side yields $$ \frac12 + \sum_{m=1}^\infty (-1)^m x^m = \frac12 + \frac{-x}{1+x} = \frac{1-x}{2+2x}. $$ Suppose we knew the formula $$ \sum_{m=0^\infty} x^m \sum_{k=0}^m (-1)^k 2^{2k-1}\binom{m+k}{2k} = \frac{1-x}{2 (x+1)^2}. $$ Then the left-hand side equals $$ \sum_{m=0^\infty} x^m \sum_{k=0}^m (-1)^k 2^{2k-1}\binom{m+k}{2k} + x \sum_{m=0^\infty} x^{m-1} \sum_{k=0}^m (-1)^k 2^{2k-1}\binom{m-1+k}{2k} = \frac{1-x}{2 (x+1)^2} + x\frac{1-x}{2 (x+1)^2} = \frac{1-x}{2x+2}. $$

To establish the necessary formula, switch the order of summation on the left-hand side to get \begin{align*} \sum_{k=0}^\infty (-1)^k 2^{2k-1} \sum_{m=k^\infty} x^m \binom{m+k}{2k} &= \sum_{k=0}^\infty (-1)^k 2^{2k-1} \sum_{m=0^\infty} x^{m+k} \binom{m+2k}{2k} \\\ &= \sum_{k=0}^\infty (-1)^k 2^{2k-1} x^k \sum_{m=0^\infty} x^m \binom{m+2k}{m} \\\ &= \sum_{k=0}^\infty (-1)^k 2^{2k-1} x^k \sum_{m=0^\infty} x^m (-1)^m \binom{-2k-1}{m} \\\ &= \sum_{k=0}^\infty (-1)^k 2^{2k-1} x^k (1-x)^{-2k-1} \\\ &= \frac1{2(1-x)} \sum_{k=0}^\infty \bigg(\frac{-4x}{1-x}^2\bigg)^k \\\ &= \frac1{2(1-x)} \frac1{1-(-4x/(1-x)^2)} = \frac{1-x}{2 (x+1)^2} \end{align*} as desired.

share|cite|improve this answer
Is ${-1\choose 0}=1$? If so, I don't see why you say 1/2 for $m=0$, unless you took ${-1\choose 0}=0$. – TCL May 1 '13 at 4:07
Both Maple and Mathematica return 1 for ${-1\choose 0}$. – TCL May 1 '13 at 4:08
I think if you take ${-1\choose 0}$ as 1, you will still get a proof. – TCL May 1 '13 at 12:32
Yeah, I think $\binom{-1}0=1$ makes more sense, in hindsight. That means both generating functions need to be increased by $1/2$, turning them into $1/(x+1)$, which is even nicer. Proof still works.... – Greg Martin May 2 '13 at 1:40

Suppose we seek to evaluate $$\sum_{k=0}^m (-1)^k 2^{2k-1} \left[{m+k-1\choose 2k}+{m+k\choose 2k}\right].$$

There are two pieces here, the first is $$\frac{1}{2}\sum_{k=0}^m (-1)^k 2^{2k} {m+k-1\choose 2k}$$

and the second is $$\frac{1}{2}\sum_{k=0}^m (-1)^k 2^{2k} {m+k\choose 2k}.$$

We treat these in turn.

Introduce $${m+k-1\choose 2k} = {m+k-1\choose m-1-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-k}} (1+z)^{m+k-1} \; dz.$$

This is zero when $k\ge m$ so we may let $k$ go to infinity.

We thus get for the first piece $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^m} \sum_{k\ge 0} (-1)^k 2^{2k} z^k (1+z)^k \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^m} \frac{1}{1+4z(1+z)} \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^m} \frac{1}{(2z+1)^2} \; dz.$$

Similarly the second piece is $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{m+1}} \frac{1}{(2z+1)^2} \; dz.$$

Adding these we obtain $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^m} \left(1+\frac{1+z}{z}\right) \frac{1}{(2z+1)^2} \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^{m+1}} \frac{1}{2z+1} \; dz.$$

Extracting the residue we get $$\frac{1}{2} \sum_{q=0}^{m-1} {m-1\choose q} (-1)^{m-q} 2^{m-q} = -\sum_{q=0}^{m-1} {m-1\choose q} (-1)^{m-1-q} 2^{m-1-q} \\ = - (1-2)^{m-1} = (-1)^m.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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