Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
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
1  
@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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.