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$
  • $\begingroup$ $w^r=1$ or $w^n=1$.? $\endgroup$ – Nosrati Mar 4 '17 at 11:05
  • $\begingroup$ sorry, it's n $\omega^n$ $\endgroup$ – Mclalalala Mar 4 '17 at 11:07
  • $\begingroup$ @MyGlasses Do you have some thoughts? $\endgroup$ – Mclalalala Mar 4 '17 at 11:07
  • $\begingroup$ Is your example true.? $n=3$.? $\endgroup$ – Nosrati Mar 4 '17 at 11:11
  • $\begingroup$ yes, and also $n=4$ $\endgroup$ – Mclalalala Mar 4 '17 at 11:12
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$
  • $\begingroup$ so it's just exactly $2^n$ $\endgroup$ – Mclalalala Mar 4 '17 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 '17 at 16:06
  • $\begingroup$ Oh my god, but where is the mistake? $\endgroup$ – Mclalalala Mar 4 '17 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 '17 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 '17 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.