Given $$(1+x)^n= \binom {n}{0} + \binom{n}{1} x+ \binom{n}{2} x^2+ \cdots + \binom {n}{n} x^n.$$ Find the value $\binom {n}{0} + \binom{n}{4} + \binom{n}{8} + \cdots $, where $n$ is a positive integer.

I tried to use negative $x$ and even $i$ but could not eliminate $\binom{n}{2} $ term.


Hint: What is $(1+1)^n+(1-1)^n+(1+i)^n+(1-i)^n$?


This answer repeatedly takes advantage of one fact,


Returns $1$ for a nonnegative even integer, and $0$ for a nonnegative odd integer.

Our sum is,

$$\sum_{k=0,\text{even}}^{n/2} {n \choose 2k}$$

$$=\sum_{k=0}^{n/2} \frac{1+(-1)^k}{2}{n \choose 2k}$$

$$=\frac{1}{2}\left(\sum_{k=0}^{n/2} {n \choose 2k}+\sum_{k=0}^{n/2} (-1)^k {n \choose 2k} \right)$$

Now notice,

$$f(x):=\sum_{k=0}^{n/2} {n \choose 2k}x^{2k}$$

$$=\sum_{k=0,\text{even}}^{n} {n \choose k} x^k$$

$$=\sum_{k=0}^{n} \frac{1+(-1)^k}{2}{n \choose k}x^k$$


$$=\frac{1}{2}\left((1+x)^n+(1-x)^n \right)$$


$$f(i)=\sum_{k=0}^{n/2} {n \choose 2k} (-1)^k$$

And so our sum is,


$$=\frac{1}{4}\left(2^n+(1+i)^n+(1-i)^n \right)$$

A simpler way: Notice $1,-1,i,-i$ are the $4$ (fourth) roots of unity. Then considering, $\frac{1+(-1)^k+i^k+(-i)^k}{4}=1$ when $k$ a negative integer is divisible by $4$ but equal to zero when $k$ is not divisible by $4$, we easily get the answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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