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

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$$

• $w^r=1$ or $w^n=1$.? – Nosrati Mar 4 '17 at 11:05
• sorry, it's n $\omega^n$ – Mclalalala Mar 4 '17 at 11:07
• @MyGlasses Do you have some thoughts? – Mclalalala Mar 4 '17 at 11:07
• Is your example true.? $n=3$.? – Nosrati Mar 4 '17 at 11:11
• yes, and also $n=4$ – Mclalalala Mar 4 '17 at 11:12

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$.

• so it's just exactly $2^n$ – Mclalalala Mar 4 '17 at 15:25
• My bad, made some mistakes in my calculations. It turns out to be $2n$. Wolfram verifies for the case $n = 4$. wolframalpha.com/input/… – Yiyuan Lee Mar 4 '17 at 16:06
• Oh my god, but where is the mistake? – Mclalalala Mar 4 '17 at 16:09
• I confused terms of the inner sum with the outer sum, and forgot to consider the case when $i = n$ for which the geometric sum would fail as it will have a denominator of $1 - w^i = 1 - w^n = 0$. But it's fixed now :) – Yiyuan Lee Mar 4 '17 at 16:12
• so the conclusion was $\sum_{k\ge 0}^{n-1}(1+w^k)^n$ =2n+2 right – Mclalalala Mar 4 '17 at 16:16