# Proving the combinatorial identity: $\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$

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

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.

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

-