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?
 A: 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.
A: 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.$$
