How to understand this combinatorially: $\sum^{2k}_{i=0} \binom{4k}{2i} (-1)^{i}=2^{2k}(-1)^{k}$ The TAs in my department are stuck in assisting an undergraduate with the following problem:
$$\sum^{2k}_{i=0} C^{4k}_{2i}(-1)^{i}=2^{2k}(-1)^{k}.$$
We tried to solve this via induction (obviously failed), via various combinatorial identities, via generating functions, etc. Aside from the fact that nothing works, we also do not know how to solve this nicely by using some combinatorial interpretation given this is some undergraudate's HW. I venture to ask in here for I want to see how it can be properly understood.  
 A: I'll rewrite the identity as
$$\sum_{k=0}^{2n} {4n \choose 2k} (-1)^k = 2^{2n} (-1)^n$$
because I'm about to use $i$ for something else. Write this as
$$\sum_{k=0}^{4n} {4n \choose k} a_k = 4^n (-1)^n$$
where $a_k$ is the sequence of period $4$ which is equal to $0$ when $k$ is odd and which satisfies $a_{2k} = (-1)^k$.
Claim: $$a_k = \frac{i^k + (-i)^k}{2}.$$
This is essentially an application of the discrete Fourier transform. In the high school competition circuit it is sometimes known as the "roots of unity filter." 
Corollary: The LHS of the identity evaluates to 
$$\frac{(1 + i)^{4n} + (1 - i)^{4n}}{2}.$$
Since $(1 \pm i)^2 = \pm 2i$ we have $(1 \pm i)^4 = -4$, hence the LHS of the identity evaluates to $(-4)^n$ as desired. 
A: It can be proved by induction on $k$:
$$\begin{align*}
\sum^{2k}_{i=0}\binom{4k}{2i}(-1)^{i}&=\sum_{i=0}^{2k}\left(\sum_{j=0}^4\binom4j\binom{4k-4}{2i-j}\right)(-1)^i\\
&=\sum_{j=0}^4\binom4j\sum_{i=0}^{2k}\binom{4k-4}{2i-j}(-1)^i\\
&=\sum_{i=0}^{2k}\binom{4k-4}{2i}(-1)^i+4\sum_{i=0}^{2k}\binom{4k-4}{2i-1}(-1)^i+6\sum_{i=0}^{2k}\binom{4k-4}{2i-2}(-1)^i\\
&\qquad\qquad+4\sum_{i=0}^{2k}\binom{4k-4}{2i-3}(-1)^i+\sum_{i=0}^{2k}\binom{4k-4}{2i-4}(-1)^i\\
&=\sum_{i=0}^{2k-2}\binom{4k-4}{2i}(-1)^i+6\sum_{i=1}^{2k-1}\binom{4k-4}{2i-2}(-1)^i+\sum_{i=2}^{2k}\binom{4k-4}{2i-4}(-1)^i\\
&\qquad\qquad+4\sum_{i=1}^{2k-2}\binom{4k-4}{2i-1}(-1)^i+4\sum_{i=2}^{2k-1}\binom{4k-4}{2i-3}(-1)^i\\
&=\sum_{i=0}^{2k-2}\binom{4k-4}{2i}(-1)^i+6\sum_{i=0}^{2k-2}\binom{4k-4}{2i}(-1)^{i+1}+\sum_{i=0}^{2k-2}\binom{4k-4}{2i}(-1)^i\\
&\qquad\qquad+4\sum_{i=1}^{2k-2}\binom{4k-4}{2i-1}(-1)^i+4\sum_{i=1}^{2k-2}\binom{4k-4}{2i-1}(-1)^{i+1}\\
&=-4\sum_{i=0}^{2k-2}\binom{4k-4}{2i}(-1)^i\\
&=-4(-4)^{k-1}\\
&=(-4)^k\;.
\end{align*}$$
A: Here's a short proof.
$$\sum_{k=0}^{4n} \binom{4n}{k} i^k = (1+i)^{4n} = \left(\sqrt{2} e^{i \pi /4}\right)^{4n} = 4^n e^{i n \pi} = 4^n \left(\cos (n \pi) + i\sin (n \pi)\right) = (-4)^n.$$
Equating real and imaginary parts yields both the OP's identity
$$\sum_{k=0}^{2n} \binom{4n}{2k} (-1)^k = (-4)^n$$
as well as the bonus identity
$$\sum_{k=0}^{2n-1} \binom{4n}{2k+1} (-1)^k = 0.$$
The idea here is of course similar to that in Qiaochu Yuan's answer.
