Roots of unity filter, identity involving $\sum_{k \ge 0} \binom{n}{3k}$

How do I see that$$\sum_{k \ge 0} \binom{n}{3k} = (1 + 1)^n + (\omega + 1)^n + (\omega^2 + 1)^n,$$where $\omega = \text{exp}\left({2\over3}\pi i\right)$? What is the underlying intuition behind this equality?

Solution 1:

The first thing we need is the binomial theorem which says that

$$(1+x)^n = \sum_{k\geq 0}^n{n\choose k} x^k = \sum_{k\geq 0}{n\choose k} x^k$$

where the last equality follows since ${n\choose k} \equiv 0$ for all $k > n$.

Next we have that for any sequence $a_n$ we can split the sum of it over all the integers into a sum over their respective residue classes $\mod 3$ so that $$\sum_{k\geq 0}a_k = \sum_{k\geq 0}a_{3k} + \sum_{k\geq 0}a_{3k+1} + \sum_{k\geq 0}a_{3k+2}$$

The last thing we need is that $\omega^3 = 1$ and $1+\omega + \omega^2 = 0$ when $\omega = e^{\frac{2\pi i}{3}}$. The first equality is obvious, and the second can be found from the sum of a geometrical series $1+\omega+\omega^2 = \frac{\omega^3-1}{\omega-1} = 0$.

With these ingredients we can now calculate

$$\matrix{(1+1)^n + (1+\omega)^n + (1+\omega^2)^n &=& \sum_{k\geq 0}{n\choose k}[1 + \omega^k + \omega^{2k}] \\&=& \sum_{k\geq 0}{n\choose 3k}[1 + \omega^{3k} + \omega^{6k}] \\&+& \sum_{k\geq 0}{n\choose 3k+1}[1 + \omega^{3k+1} + \omega^{6k+2}]\\&+& \sum_{k\geq 0}{n\choose 3k}[1 + \omega^{3k+2} + \omega^{6k+4}]\\&=&\sum_{k\geq 0}{n\choose 3k}[1 + 1 + 1]\\&+&\sum_{k\geq 0}{n\choose 3k+1}[1 + \omega + \omega^{2}]\\&+&\sum_{k\geq 0}{n\choose 3k+2}[1 + \omega^{2} + \omega]\\&=&3\sum_{k\geq 0}{n\choose 3k}}$$

The identity can be generalized. If we take $\omega = e^{\frac{2\pi i}{N}}$ then the same type of derivation as above gives us

$$2^n + (1+\omega)^n + \ldots + (1+\omega^{N-1})^n = N\sum_{k\geq 0}{n\choose Nk}$$