Problem source

Let $\omega=\mathrm{e}^{2\pi\mathrm{i}/3}.$ Show that $1+\omega+\omega^{2}=0$ and calculate the modulus and argument of $1+\omega^{2}.$ 
Let $n$ be a positive integer. By evaluating $(1+\omega^{r})^{n}$ in two ways, taking $r=1,2$ and $3$, or otherwise, prove that 
\[
\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots+\binom{n}{k}=\frac{1}{3}\left(2^{n}+2\cos\left(\frac{n\pi}{3}\right)\right),
\]
where $k$ is the largest multiple of $3$ less than or equal to $n$.
Without using a calculator, evaluate 
\[
\binom{25}{0}+\binom{25}{3}+\cdots+\binom{25}{24}
\]
and 
\[
\binom{24}{2}+\binom{24}{5}+\cdots+\binom{24}{23}\,.
\]
{[}$2^{25}=33554432.${]}

Solution source

Since $\omega^3 = 1$ and $\omega \neq 1$ we must have that $(\omega-1)(1 + \omega + \omega^2) = 0$ but by dividing by $\omega - 1$ we obtain the desired result.

$1+\omega^2 = -\omega$ so $|1 + \omega^2| = |-\omega| = 1$ and $\arg ( 1 + \omega^2) = \arg(-\omega) = \pi - \frac{2\pi}{3} = \frac{\pi}{3}$

\begin{align*}
&& (1 + 1)^n &= \sum_{k=0}^n \binom{n}{k}\\
&& (1+ \omega)^n &= \sum_{k=0}^n \binom{n}{k} \omega^{k} \\
&& (1+ \omega^2)^n &= \sum_{k=0}^n \binom{n}{k} \omega^{2k} \\
\Rightarrow && 2^n+(-\omega^2)^n + (-\omega)^n &= \sum_{k=0, k \equiv 0 \pmod{3}}^n (1+1+1)\binom{n}{k} + \sum_{k=0, k \equiv 1 \pmod{3}}^n (1 + \omega + \omega^2) \binom{n}{k} + \sum_{k=0, k \equiv 2 \pmod{3}}^n (1 + \omega^2 + \omega) \binom{n}{k} \\
\Rightarrow && 2^n +((-\omega)^n)^{-1}+(-\omega)^n &= \sum_{k=0, k \equiv 0 \pmod{3}}^n \binom{n}{k} 
\end{align*}

$2^n +((-\omega)^n)^{-1}+(-\omega)^n = 2^n + 2 \textrm{Re}(-\omega^n) = 2^n + 2 \cos \frac{n\pi}{3}$

Therefore our answer follows.

\begin{align*}
\binom{25}{0}+\binom{25}{3}+\cdots+\binom{25}{24} &= \frac13 \l 2^{25} + 2\cos (\frac{25 \pi}{3}) \r \\
&= \frac13 \l 2^{25} + 2 \cos \frac{\pi}{3} \r \\
&= \frac13 \l 2^{25} + 1 \r \\
&= \frac13 \l (4096 \cdot 4096 \cdot 2) + 1 \r \\
&= 11\,184\,811
\end{align*}

Notice that $S_2 = \binom{24}{2} + \cdots +\binom{24}{23} =  \binom{24}{1} + \cdots + \binom{24}{22} = S_1$ and $S_0 = \binom{24}0 + \cdots + \binom{24}{21} = \frac13 \l 2^{24} + 2  \r$

Therefore since $S_0 + 2 \cdot S_2 = 2^{24}$ we must have

\begin{align*}
S_2 &= \frac12 \l 2^{24} - \frac13 \l 2^{24} + 2  \r \r \\
&= \frac13 \l 2^{24} - 1 \r \\
&= \frac13 \l 16777216- 1 \r \\
&= \frac13 \cdot 16777215 \\
&= 5\,592\,405
\end{align*}