0
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ so it's just exactly $2^n$ $\endgroup$
    – Mclalalala
    Mar 4, 2017 at 15:25
  • $\begingroup$ My bad, made some mistakes in my calculations. It turns out to be $2n$. Wolfram verifies for the case $n = 4$. wolframalpha.com/input/… $\endgroup$
    – Yiyuan Lee
    Mar 4, 2017 at 16:06
  • $\begingroup$ Oh my god, but where is the mistake? $\endgroup$
    – Mclalalala
    Mar 4, 2017 at 16:09
  • $\begingroup$ 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 :) $\endgroup$
    – Yiyuan Lee
    Mar 4, 2017 at 16:12
  • $\begingroup$ so the conclusion was $\sum_{k\ge 0}^{n-1}(1+w^k)^n$ =2n+2 right $\endgroup$
    – Mclalalala
    Mar 4, 2017 at 16:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .