How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$ How do I find sums like these?--
$$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$
that is, when there is a summation of binomial coefficients, but with jumps of some terms..?
 A: Use the Discrete Fourier Transform. You have:
$$ S = -1+\sum_{n\equiv 0\pmod{5}}\binom{200}{n}$$
and given that $\omega$ is a primitive fifth root of unity,
$$ \begin{eqnarray*}S &=& -1+\frac{1}{5}\sum_{n=0}^{200}\binom{200}{n}(1+\omega^n+\omega^{2n}+\omega^{3n}+\omega^{4n})\\&=&-1+\frac{2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}}{5}\\&=&-1+\frac{2^{200}+2L_{200}}{5}, \end{eqnarray*}$$
where $L_{200}$ is the $200$th Lucas number.
A: Note that $(1+x)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}x^k$. Let $\omega = e^{i2\pi/5}$
$(1+1)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}1^k$
$(1+\omega)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^k$
$(1+\omega^2)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{2k}$
$(1+\omega^3)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{3k}$
$(1+\omega^4)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{4k}$
Now, since $1^k+\omega^k+\omega^{2k}+\omega^{3k}+\omega^{4k} = 5$ if $k$ is a multiple of $5$ and $0$ otherwise, we can add those $5$ equations together to get: 
$\displaystyle\sum_{\substack{k = 0 \\ 5 | k}}^{200}5\dbinom{200}{k} = \sum_{k = 0}^{40}5\dbinom{200}{5k} = 2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}$. 
Divide by $5$ and subtract $\dbinom{200}{200} = 1$ to get: 
$\displaystyle\sum_{k = 0}^{39}\dbinom{200}{5k} = \dfrac{1}{5}\left(2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}\right)-1$. 
Using the fact that $1+\omega = \phi e^{i\pi/5}$ and $1+\omega^2 = \frac{1}{\phi} e^{i2\pi/5}$, where $\phi = \dfrac{1+\sqrt{5}}{2}$, this simplifies to: 
$\displaystyle\sum_{k = 0}^{39}\dbinom{200}{5k} = \dfrac{1}{5}\left(2^{200}+2\phi^{200}+2\phi^{-200}\right)-1$
