Find the value $\binom {n}{0} + \binom{n}{4} + \binom{n}{8} + \cdots $, where $n$ is a positive integer.

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.

Solution 1:

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

Solution 2:

This answer repeatedly takes advantage of one fact,

$$g(k)=\frac{(-1)^k+1}{2}$$

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)$$

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

But

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

And so our sum is,

$$\frac{1}{2}(f(1)+f(i))$$

$$=\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.