Equal number of $n$th roots of unity within character values $f_1(a), \dots, f_m(a)$. (Apostol exercise 6.12 Intro to ANT) This problem is taken from Exercise 6.12 from Apostol's "Introduction to Analytic Number Theory".
Verbatim, the problem states

Let $f_1, \dots, f_m$ be the characters of a finite group $G$ of order $m$, and let $a$ be an element of $G$ of order $n$. Theorem 6.7 shows that each number $f_r(a)$ is an $n$th root of unity. Prove that every $n$th root of unity occurs equally often among the numbers $f_1(a), f_2(a), \dots, f_m(a)$.

Theorem 6.7 above simply states that every $f_r(a)$ is an $n$th root of unity.
The case of $n = 1$ is trivial, I'll assume $n > 1$ throughout the rest of this question. Apostol gives as a hint that evaluation of the sum
$$\sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n}$$
in "two different ways" shows how many $f_r(a) = e^{2\pi i/n}$. The sum above evaluates to $m$, since
$$S = \sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n} = \sum_{k=1}^n e^{-2\pi ik/n} \sum_{r=1}^m f_r(a^k), $$
and, by Theorem 6.13,
$$\sum_{r=1}^m f_r(a^k) = \begin{cases}
m & k = n \\
0 & \text{otherwise}.
\end{cases}$$
Therefore, $S$ vanishes for $k = 1, 2, \dots, n-1$, which implies $S = me^{-2\pi i} = m$.
The "second way" to evaluate $S$ is to notice that the sum
$$\sum_{k=1}^n [f_r(a)e^{-2\pi i/n}]^k$$
equals $n$ only when $f_r(a) = e^{2\pi i/n}$, otherwise, $f_r(a)e^{-2\pi i/n}$ is some non-one $n$th root of unity $\omega$ and the sum above equals
$$\sum_{k=1}^n \omega^k = 0$$
by properties of roots of unity. Thus, since $S = m$, if $\alpha$ represents the number of $f_r(a) = e^{2\pi i/n}$, then $m = \alpha n$, or $\alpha  =m/n$.
However, what would lead one to consider the sum $S$ in the first place? Where did it come from? It seems almost as if $S$ appeared out of "thin air". Is there another way to prove this statement without the evaluation of $S$?
Thanks in advance!

Here is a proof, using only facts from Chapter 6 of Apostol, and using its notation. Let $a\in G$ have order $n$.
The characters form a group under multiplication. Therefore, if $f_1,\dots,f_r$ are the characters, then multiplying by $f_i$ simply permutes the characters. In particular, for any fixed $a\in G$, it permutes the values in the set
$$X=\{f_j(a)\mid 1\leq j\leq r\}.$$
This is the set we wish to prove is simply each $n$th root of unity appearing $r/n$ times. Suppose that $f_i(a)$ is a primitive $n$th root of unity. Then multiplying by $f_i$ has the effect of multiplying all elements in the set $X$ by $f_i(a)$, a primitive $n$th root of unity. The only way such a multiplication can preserve $X$ is if $X$ is uniform.
Thus we must check that there is such an element $f_i$. If not, then all of the $f_j(a)$ (since it is closed under multiplication as the $f_i$ form a group) must be all $m$th roots of unity for some $m$ strictly dividing $n$ (as they are already $n$th roots of unity).
But now, $a^{n/m}$ is a non-trivial element, and $f_i(a^{n/m})=1$ for all $1\leq i\leq r$. By Theorem 6.10 from Apostol (column orthogonality relation), $a^{n/m}$ is the identity, a contradiction.
