# A combinatorial identity

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?

-

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}.$$
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