# What is the sum of binomial coefficients? [duplicate]

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

## marked as duplicate by ArsenBerk, Brahadeesh, Adrian Keister, Scientifica, NamasteOct 2 '18 at 22:42

• @TheSilverDoe : I think the answer to "Where does your sum finish?" is clear. It continues, but only finitely many terms are non-zero. $\qquad$ – Michael Hardy Oct 2 '18 at 15:04
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$$.