Maths Olympiad Prep

Library / /815 of 860

Algebra Difficulty 5.6 AIME, harder Find the answer

Let zz be a non-real complex number with z23=1z^{23}=1. Compute k=02211+zk+z2k \sum_{k=0}^{22} \frac{1}{1+z^{k}+z^{2 k}}

A number or a short expression. Spacing and $ signs are ignored.

Solution

First solution: Note that k=02211+zk+z2k=13+k=1221zk1z3k=13+k=1221(z24)k1z3k=13+k=122=07z3k \sum_{k=0}^{22} \frac{1}{1+z^{k}+z^{2 k}}=\frac{1}{3}+\sum_{k=1}^{22} \frac{1-z^{k}}{1-z^{3 k}}=\frac{1}{3}+\sum_{k=1}^{22} \frac{1-\left(z^{24}\right)^{k}}{1-z^{3 k}}=\frac{1}{3}+\sum_{k=1}^{22} \sum_{\ell=0}^{7} z^{3 k \ell} 3 and 23 are prime, so every non-zero residue modulo 23 appears in an exponent in the last sum exactly 7 times, and the summand 1 appears 22 times. Because the sum of the 23 rd roots of unity is zero, our answer is 13+(227)=463\frac{1}{3}+(22-7)=\frac{46}{3}. Second solution: For an alternate approach, we first prove the following identity for an arbitrary complex number aa : k=0221azk=23a22a231 \sum_{k=0}^{22} \frac{1}{a-z^{k}}=\frac{23 a^{22}}{a^{23}-1} To see this, let f(x)=x231=(x1)(xz)(xz2)(xz22)f(x)=x^{23}-1=(x-1)(x-z)\left(x-z^{2}\right) \ldots\left(x-z^{22}\right). Note that the sum in question is merely f(a)f(a)\frac{f^{\prime}(a)}{f(a)}, from which the identity follows. Now, returning to our original sum, let ω1\omega \neq 1 satisfy ω3=1\omega^{3}=1. Then k=02211+zk+z2k=1ω2ωk=0221ωzk1ω2zk =1ω2ω(k=0221ωzkk=0221ω2zk) =1ω2ω(23ω22ω23123ω44ω461) =23ω2ω(ωω21ω2ω1) =23ω2ω(ω2ω)(ωω2)2ωω2 =463 \begin{aligned} \sum_{k=0}^{22} \frac{1}{1+z^{k}+z^{2 k}} & =\frac{1}{\omega^{2}-\omega} \sum_{k=0}^{22} \frac{1}{\omega-z^{k}}-\frac{1}{\omega^{2}-z^{k}} \ & =\frac{1}{\omega^{2}-\omega}\left(\sum_{k=0}^{22} \frac{1}{\omega-z^{k}}-\sum_{k=0}^{22} \frac{1}{\omega^{2}-z^{k}}\right) \ & =\frac{1}{\omega^{2}-\omega}\left(\frac{23 \omega^{22}}{\omega^{23}-1}-\frac{23 \omega^{44}}{\omega^{46}-1}\right) \ & =\frac{23}{\omega^{2}-\omega}\left(\frac{\omega}{\omega^{2}-1}-\frac{\omega^{2}}{\omega-1}\right) \ & =\frac{23}{\omega^{2}-\omega} \frac{\left(\omega^{2}-\omega\right)-\left(\omega-\omega^{2}\right)}{2-\omega-\omega^{2}} \ & =\frac{46}{3} \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.