Summation involving binomial coefficients: $\sum_{i=0}^{100} \binom{300}{3i}$ I came across the following sum online and have spent awhile trying to compute it:
$$\sum_{i=0}^{100} \binom{300}{3i}$$ 
Based on a pattern I noticed, the answer should be $\frac{2^{300}}{3}$ rounded up. However I cannot figure out how to actually solve for the answer. The problem gave the hint of using the binomial theorem: $(a+b)^n=\sum_{k=0}^{n} \binom{n}{k} a^{k} b^{n-k}$. For example, the problem before it was $\sum_{i=0}^{100} \binom{100}{i}$ which would just end up being
$$\sum_{i=0}^{100} \binom{100}{i}=\sum_{i=0}^{100} \binom{100}{i}1^{k} 1^{100-k}=(1+1)^{100}=2^{100}.$$
The $3i$ in the denominator is the real issue here because I can't seem to manipulate it to resemble the binomial theorem. I have even tried expanding it out to look for patterns but to no avail. Anyone have any hints or tips?
 A: Hints:


*

*Consider the function $f(x):=\sum_{i=0}^{300}\limits\binom{300}{i}x^i=(1+x)^{300}$

*Consider the value of $\frac 13\left(f(1)+f(\omega)+f(\omega^2)\right)$ where $\omega$ denotes a primitive cube root of unity.

*Recall that $1+\omega^n+\omega^{2n}=\begin{cases}0~\forall~n\not\equiv 0\pmod3\\ 3~\forall~n\equiv 0\pmod3\end{cases}$



Added a generalization:
Notice that if you go a way further, you can generalize this problem. Consider positive integers $n$ and $d$ such that $d\leq n$.
You can generalize the above problem, i.e., compute the sum $\displaystyle\mathcal{S}(n,d)=\sum\limits_{i=0}^{\lfloor n/d\rfloor}\dbinom{n}{di}$
For this, you would be considering $f(x):=\sum\limits_{i=0}^n\binom{n}{i}x^i=(1+x)^n$ and we'll have,
$$\mathcal{S}(n,d)=\frac 1d\sum_{i=0}^{d-1}f(\omega^i)$$
where $\omega$ denotes a primitive $d^{\textrm{th}}$ root of unity.
A result used to write the above expression for $\mathcal{S}(n,d)$ is,
$$\sum_{i=0}^{d-1}\omega^{ik}=\begin{cases}0~\forall~k\not\equiv 0\pmod{d}\\ d~\forall~k\equiv 0\pmod{d}\end{cases}$$
The problem at hand would be just computing $\mathcal{S}(300,3)$.
