Binomial sum with index as Arithmetic Progression 
Consider a binomial sum of form,
$$ S = \sum_{k=1}^{\infty} \binom{n}{a_k}$$
Where,
$$ a_k  = a_o + (k-1) d$$ w/ $a_o \geq 0 $ $ d \geq 0$

An immediate simplification is that for terms with, $ a_k \geq n$ are zero. So, if there is a $j$ such that $n \in [a_j,a_{j+1} ]$ , then the sum's upper index turns to:
$$ S = \sum_{k=1}^{j} \binom{n}{a_k}$$
A brute force way to calculate would be to directly add them after that, but is there a simpler way to solve this?
The person who sent me this problem mentioned that I could use roots of unity to solve this.. but I'm not sure how that relates to here...
 A: The standard method to solve these involves the roots of unity filter (or finite Fourier analysis for the pretentious).
The idea is to look at the polynomial $f(x)=x^{d-a_0}(1+x)^n$. This has the property that the coefficient of $x^{dk}$ is $\binom{n}{a_0+dk}$. So if we could somehow extract only the coefficients of $x^{dk}$ and sum them, we would be done.
The trick is to consider $$\frac{f(1)+f(\omega)+\dots+f\left(\omega^{d-1}\right)}{d},$$ where $\omega=\exp(2i\pi/d)$ is the $d$-th root of unity. Can you see why this extracts only the coefficients of $x^{dk}$ in the sum?

To make this concrete, consider the following example:
$$\sum_{k\geq0}\binom{2021}{3k+1}.$$
Take the polynomial $f(x)=x^2(1+x)^{2021}$, so writing $\omega=\exp(2i\pi/3)$, the sum we want is
$$\frac{(1+1)^{2021}+\omega^2(1+\omega)^{2021}+\omega(1+\omega^2)^{2021}}{3}.$$
Now in general, at this point you'd just convert to polar form $1+\omega^m=re^{i\theta}$ and bash it out, but for $n=3$ you can take advantage of the neat trick that $1+\omega+\omega^2=0$ to make the calculation easier:
\begin{align*}
\frac{(1+1)^{2021}+\omega^2(1+\omega)^{2021}+\omega(1+\omega^2)^{2021}}{3} &= \frac{1}{3}\left[2^{2021}+\omega^2(-\omega^2)^{2021}+\omega(-\omega)^{2021}\right] \\
&= \frac{1}{3}\left[2^{2021}-\omega^{4044}-\omega^{2022}\right] \\
&=\frac{1}{3}\left[2^{2021}-2\right].
\end{align*}
