Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

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.