Roots of Unity Filters Suppose we want to evaluate
$$\sum_{k\geq 0} \binom{n}{3k}$$
This can be done using roots of unity filters, i.e. showing the sum is equivalent to:
$$\frac{(1+1)^n+(1+\omega)^n+(1+\omega^2)^n}{3}$$
where $\omega$ is a primitive 3rd root of unity.
Using the fact that $1+\omega+\omega^2=0$, we can show that this is equivalent to
$$\frac{2^n+(-\omega^2)^n+(-\omega)^n}{3}$$
Depending on whether $n$ is even or odd, we get that this sum is equal to either $\frac{2^n-1}{3}$ or $\frac{2^n+1}{3}$
Can we use the same trick to evaluate the following sums?
$$\sum_{k\geq 0}\binom{n}{3k+1}, \sum_{k\geq 0}\binom{n}{3k+2}$$
Also, can this idea be generalized? 
I would appreciate any thoughts or ideas.
 A: $$\sum \binom{n}{3k+1} = \frac{1^2 (1+1)^n + \omega^2(1+\omega)^n + \omega(1+\omega^2)^n}{3}$$
Basically, apply the same approach to $f(x)=x^2(1+x)^n$.
Similarly, taking $g(x)=x(1+x)^n$ we get:
$$\sum\binom{n}{3k+2}=\frac{1(1+1)^n + \omega(1+\omega)^n + \omega^2(1+\omega^2)^n}{3}$$
You should be able to get nice formula for these, depending on $n\bmod 3$.
A: Here is Pascal's Triangle for the first $8$ rows
$$1$$
$$1, 1$$
$$1,2,1$$
$$1,3,3,1$$
$$1,4,6,4,1$$
$$1,5,10,10,5,1$$
$$1,6,15,20,15,6,1$$
$$1,7,21,35,35,21,7,1$$
Then your sequence $S_n$ of $\binom{n}{3k}$ is $\{1,1,1,2,5,11,22,43\}$
Then your sequence $\Sigma S_n$ of $\binom{n}{3k}$ (the partial sums of $S_n$) is $\{1,2,3,5,10,21,43, 86\}$
But what happens if we look at $T_n=\binom{n}{3k+1}$?
Then $T_n=\{0,1,2,3,5,10,21,43\}$
What do you notice, and can you prove a link?
Or $U_n=\binom{n}{3k+2}$?
$U_n=\{0,0,1,3,6,11,21,42\}$ 
Now consider $\Sigma T_n$....noticing anything??????
Hopefully you can see that $\Sigma S_n=T_{n+1}$
and then you can see that $\Sigma T_n=U_{n+1}$
and finally $\Sigma \Sigma S_n=U_{n+2}$
