How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$

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$

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.

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{S\equiv\sum_{k = 0}^{39}{200 \choose 5k}:\ {\large ?}}$

$$ \mbox{Note that}\quad S = -1+ \color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}}\tag{1} $$

\begin{align} &\color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}} =\sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{200} \over z^{5k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{200} \over z} \sum_{k = 0}^{\infty}\pars{1 \over z^{5}}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{200} \over z} \,{1 \over 1 - 1/z^{5}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{z^{4}\pars{1 + z}^{200} \over z^{5} - 1} \,{\dd z \over 2\pi\ic} \end{align}

The integrand simple poles are the five roots of $\ds{z^{5} - 1 = 0}$. Namely, $$ z_{n} = \expo{2n\pi\ic/5}\,,\qquad\qquad n=-2,-1,0,1,2. $$ Then,

\begin{align} &\color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}} =\sum_{n = -2}^{2}\lim_{z \to z_{n}} \bracks{\pars{z - z_{n}}\,{z^{4}\pars{1 + z}^{200} \over z^{5} - 1}} ={1 \over 5}\sum_{n = -2}^{2}\pars{1 + z_{n}}^{200} \\[5mm]&={1 \over 5}\sum_{n = -2}^{2}\pars{1 + \expo{2n\pi\ic/5}}^{200} ={1 \over 5}\sum_{n = -2}^{2}\pars{\expo{-n\pi\ic/5} + \expo{n\pi\ic/5}}^{200} \\[5mm]&={2^{200} \over 5}\sum_{n = -2}^{2}\cos^{200}\pars{n\,{\pi \over 5}} ={2^{200} \over 5}\bracks{1 + 2\cos^{200}\pars{\pi \over 5} +2\cos^{200}\pars{2\pi \over 5}} \end{align}

Replacing this result in $\pars{1}$:

\begin{align} S&\equiv\color{#66f}{\large\sum_{k = 0}^{39}{200 \choose 5k}}\ {\Large =}\ \color{#66f}{\large{2^{200} \over 5} - 1 + {2^{201} \over 5}\,\bracks{\cos^{200}\pars{\pi \over 5} +\cos^{200}\pars{2\pi \over 5}}} \\[5mm]&\approx {\tt 3.2139 \times 10^{59}} \end{align}