What is the sum of binomial coefficients?

Question

$$\binom n0 + \binom n4 + \binom n8 + \cdots$$ Any hints?

Answer 1

Hint: set $\omega_r=\exp(2\pi i/r)$, then look at

$$\sum_{j=0}^{r-1} (1+\omega_r^j)^n=\sum_{k=0}^n {n \choose k} \sum_{j=0}^{r-1} \omega_r^{jk}$$

That inner sum can be evaluated explicitly; it will turn out to vanish when $k$ is not a multiple of $r$.

Then set $r=4$.