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

-

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

-
The first step is$\binom{4k}{2i}=\sum_{j=0}^{4} \binom{4}{j} \binom{4k-4}{2i-j}$. Can you explain this a bit? – Alex Oct 24 '12 at 3:13
@Alex: In general $\binom{n}k=\binom{n-1}k+\binom{n-1}{k-1}$; do it again to get $\left(\binom{n-2}k+\binom{n-2}{k-1}\right)+\left(\binom{n-2}{k-1}+\binom{n-2}{k‌​-2}\right)$, or $\binom{n-2}k+2\binom{n-2}{k-1}+\binom{n-2}{k-2}$. Apply the Pascal’s triangle identity to each term again, and you get $\binom{n-3}k+3\binom{n-3}{k-1}+3\binom{n-3}{k-2}+\binom{n-3}{k-3}$. Do it one more time, and you get what I used, after you substitute $4k$ for $n$ and $2i$ for $k$. The general result, which can be proved by induction on $r$, is that $\binom{n}k=\sum_{i=0}^r\binom{r}i\binom{n-4}{k-i}$. – Brian M. Scott Oct 24 '12 at 11:09
Awesome, thanks – Alex Oct 25 '12 at 7:53
@Alex: You’re welcome. – Brian M. Scott Oct 25 '12 at 7:55

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.

-
Nice. Thanks. Need sometime to check the detail. I attempted to use $(i-i)^{4n}$, which failed to produce the period 4 sequence desired. – Bombyx mori Oct 4 '12 at 22:22

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.

-