HMMT-Feb 2013 alg, Problem 9

Let $z$ be a non-real complex number with $z^{23}=1$. Compute \[ \sum_{k=0}^{22} \frac{1}{1+z^{k}+z^{2 k}} \]

Solution: First solution: Note that \[ \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 23rd roots of unity is zero, our answer is $\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 $a$ : \[ \sum_{k=0}^{22} \frac{1}{a-z^{k}}=\frac{23 a^{22}}{a^{23}-1} \] To see this, let $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 $\frac{f^{\prime}(a)}{f(a)}$, from which the identity follows. Now, returning to our orignal sum, let $\omega \neq 1$ satisfy $\omega^{3}=1$. Then \[ \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} \] $\fbox{46 / 3}$.

Answer: 46 / 3