an approximation of the sum of roots of unity to the powers of 2

Question

How to prove that $$(1+\omega^0)+(1+\omega)^n+(1+\omega^2)^n+(1+\omega^3)^n+\cdot\cdot\cdot\cdot\cdot+(1+\omega^{r-1})^n$$ can be approximated as $2^n$, where $\omega^n=1$. For example, $$(1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n) = 2^n + (-\omega^2)^n + (-\omega)^n)$$ $$(1 + 1)^n + (1 + \omega)^n= 2^n $$

Answer 1

We need:

$$\begin{align}S &= \sum_{i = 0}^{n}{n\choose i}\left(\sum_{j = 0}^{n - 1} (w^j)^i\right)\\ &= \sum_{i = 0}^{n}{n\choose i}\left(\sum_{j = 0}^{n - 1} (w^i)^j\right)\end{align}$$

Now the inner sum is just a geometric series, and we all know that for $x \not= 1$,

$$1 + x + ... + x^{n - 1} = \frac{1 - x^n}{1 - x}$$

So we have

$$\begin{align}S &= {n\choose 0}\left(\sum_{j = 0}^{n - 1}(w^0)^j\right) + {n\choose n}\left(\sum_{j = 0}^{n - 1}(w^n)^j\right) + \sum_{i = 1}^{n - 1}{n\choose i}\left(\frac{1 - (w^i)^n}{1 - w^i}\right)\\ &= n + n + \sum_{i = 1}^{n - 1}{n\choose i}\left(\frac{1 - (w^n)^i}{1 - w^i}\right)\\ &= 2n + \sum_{i = 1}^{n - 1}{n\choose i}\left(\frac{1 - (w^n)^i}{1 - w^i}\right)\end{align}$$

Note that I've separated the case for $i = 0, n$ because $w^0, w^n = 1$ which will cause the geometric sum formula to fail.

Next, by definition $w^n = 1$ so we get

$$\begin{align}S &= 2n + \sum_{i = 1}^{n - 1}{n\choose i}\left(\frac{1 - (1)^i}{1 - w^i}\right)\\ &= 2n + \sum_{i = 1}^n {n\choose i}(0)\\ &= 2n\end{align}$$

Wolfram verifies for $n = 6$.