4.3 General power sum invariance

Theorem 4.3.1 Power sum invariance

✓

For any integers \(N \geq 1\), \(j\) with \(1 \leq j {\lt} N\), and any \(\theta \in \mathbb {R}\),

\begin{equation} \sum _{k=0}^{N-1} \cos ^j\left(\theta + \frac{2\pi k}{N}\right) \end{equation}

is independent of \(\theta \).

(See ../docs/ChebyshevCircles/Proofs/PowerSums.html#powerSumCos_invariantAPI Documentation | ../paper/chebyshev_circles.pdfPaper Theorem 4.1)

Proof sketch ▶

Expand \(\cos ^j(\theta + 2\pi k/N)\) using \(\cos \theta = (\mathrm{e}^{i\theta } + \mathrm{e}^{-i\theta })/2\). The binomial expansion yields

\begin{equation} \sum _{k=0}^{N-1} \cos ^j\left(\theta + \frac{2\pi k}{N}\right) = \frac{1}{2^j} \sum _{\ell =0}^j \binom {j}{\ell } \sum _{k=0}^{N-1} \mathrm{e}^{i(j-2\ell )(\theta + 2\pi k/N)}. \end{equation}

Factor out \(\mathrm{e}^{i(j-2\ell )\theta }\):

\begin{equation} = \frac{1}{2^j} \sum _{\ell =0}^j \binom {j}{\ell } \mathrm{e}^{i(j-2\ell )\theta } \sum _{k=0}^{N-1} \mathrm{e}^{2\pi i (j-2\ell )k/N}. \end{equation}

By Lemma 2.2.1, the inner sum is \(N\) if \(N \mid (j - 2\ell )\), and \(0\) otherwise. Since \(1 \leq j {\lt} N\), we have \(|j - 2\ell | \leq j {\lt} N\) for all \(\ell \in \{ 0, \ldots , j\} \). The only way \(N \mid (j - 2\ell )\) is if \(j - 2\ell = 0\), i.e., \(j = 2\ell \).

If \(j\) is odd, no such \(\ell \) exists, and the entire sum is zero (independent of \(\theta \)). If \(j\) is even, only the term \(\ell = j/2\) contributes, yielding

\begin{equation} \frac{N}{2^j} \binom {j}{j/2}, \end{equation}

which is independent of \(\theta \).

The formalization establishes this for small values of \(j\) explicitly (\(j = 2, 3, 4, 5, 6\)) and then proves the general case using the binomial argument above.