Solution
Every Third Binomial
Show the problem again
Compute $\binom{30}{0} + \binom{30}{3} + \binom{30}{6} + \dots + \binom{30}{30}$, the sum of $\binom{30}{k}$ over all $k$ divisible by 3. Give an exact integer.
Worked solution
The answer is 357913942. Let $\omega = e^{2\pi i/3}$. Since $1 + \omega^k + \omega^{2k}$ is 3 when $3 \mid k$ and 0 otherwise, the sum is $\frac{1}{3}\left[(1+1)^{30} + (1+\omega)^{30} + (1+\omega^2)^{30}\right]$. Now $1 + \omega = -\omega^2$, a sixth root of unity, so $(1+\omega)^{30} = \omega^{60} = 1$, and likewise $(1+\omega^2)^{30} = 1$. The sum is $(2^{30} + 2)/3 = (1073741824 + 2)/3 = 357913942$: a third of the row total plus a tiny correction from the complex terms.
Source: Classic roots-of-unity filter exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.