# 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.

• here is one such post... – Eleven-Eleven Oct 9 '16 at 1:40
• here is the OEIS of $\binom{n}{3k}$ – Eleven-Eleven Oct 9 '16 at 1:45

$$\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$$.

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}$