2 problems found
Solution:
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: 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*}