7
$\begingroup$

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.

3 Answers 3

3

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.

8

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.

  • 0
    Nice. Thanks. Need sometime to check the detail. I attempted to use $(i-i)^{4n}$, which failed to produce the period 4 sequence desired.2012-10-04
6

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

  • 0
    @Alex: You’re welcome.2012-10-25