Proof: $\sum\limits_{r=0}^{\infty}{n\choose t+rs}=\frac1s\sum\limits_{j=0}^{s-1} \left(2\cos\frac{\pi j}2\right)^n\cos\frac{\pi j(n-2t)}s$ I found somewhere on the internet (I forget where) the strange identity

For $s,t\in\Bbb Z,\quad 0\leq t<s:$
$$\sum_{r\geq0}{n\choose t+rs}=\frac1s\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}2\right)^n\cos\frac{\pi j(n-2t)}s$$ Although I do not know the restrictions on $n$, I suspect $n\in\Bbb N$.

I am attempting to prove this curious identity. I start by defining 
$$F(n;t,s)=\sum_{r\geq0}{n\choose t+rs}$$
I was thinking we could use the integral given by the Wolfram functions Site:
$${n\choose k}=\frac1{2\pi}\int_{-\pi}^\pi e^{-ikx}(1+e^{ix})^{n}dx$$
But I am unsure if I would be able validly to interchange the sum and integral signs. Other than that I thought I might be able to use my usual trick of representing the binomial as a beta integral, but I cannot seem to do that in this case. Any help would be appreciated. 
 A: The $s$-th roots of unity $\omega_j=\exp\left(\frac{2\pi ij}{s}\right), 0\leq j<s$ have the nice property to filter elements. For $s>0$ we obtain
\begin{align*}
\frac{1}{s}\sum_{j=0}^{s-1}\exp\left(\frac{2\pi ij n}{s}\right)=
\begin{cases}
1&\qquad s\mid n\\
0& \qquad otherwise
\end{cases}
\end{align*}
We can use it for series multisection of $f(z)=\sum_{r=0}^\infty a_rz^r$ to obtain
\begin{align*}
\sum_{r=0}^\infty a_{t+rs}z^{t+rs}=\frac{1}{s}\sum_{j=0}^{s-1}\omega_j^{-t}f(\omega_jz)\qquad s,t\in\mathbb{Z}, s>0, t\geq 0\tag{1}
\end{align*}

We apply (1) to $f(z)=(1+z)^n=\sum_{r=0}^n \binom{n}{r}z^r$ and obtain setting $z=1$
\begin{align*}
\color{blue}{\sum_{r=0}^n}\color{blue}{\binom{n}{t+rs}}&
=\frac{1}{s}\sum_{j=0}^{s-1}\omega_j^{-t}(1+\omega_j)^n\\
&=\frac{1}{s}\sum_{j=0}^{s-1}\exp\left(-\frac{2i\pi jt}{s}\right)\left(1+\exp\left(\frac{2i\pi j}{s}\right)\right)^n\\
&=\frac{1}{s}\sum_{j=0}^{s-1}\exp\left(\frac{i\pi j (n-2t)}{s}\right)
\left(\exp\left(-\frac{i\pi j}{s}\right)+\exp\left(\frac{i\pi j}{s}\right)\right)^n\tag{2}\\
&=\frac{1}{s}\sum_{j=0}^{s-1}\left(\cos\left(\frac{\pi j (n-2t)}{s}\right)+i\sin\left(\frac{\pi j(n-2t)}{s}\right)\right)\\
&\qquad \cdot\left(2\cos\left(\frac{\pi j}{s}\right)\right)^n\tag{3}\\
&\,\,\color{blue}{=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\left(\frac{\pi j}{s}\right)\right)^n\cos\left(\frac{\pi j(n-2t)}{s}\right)}\tag{4}
\end{align*}
  and the claim follows.

Comment:


*

*In (2) we factor out $\exp\left(\frac{\pi nj}{s}\right)$.

*In (3) we use the identities $e^{iz}=\cos(z)+i\sin(z)$ and $\cos(z)=\frac{1}{2}\left(e^{iz}+e^{-iz}\right)$.

*In (4) we skip the imaginary part (which is zero), since we know the result is real-valued.
