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 $$
-
$\begingroup$ $w^r=1$ or $w^n=1$.? $\endgroup$– NosratiMar 4, 2017 at 11:05
-
$\begingroup$ sorry, it's n $\omega^n$ $\endgroup$– MclalalalaMar 4, 2017 at 11:07
-
$\begingroup$ @MyGlasses Do you have some thoughts? $\endgroup$– MclalalalaMar 4, 2017 at 11:07
-
$\begingroup$ Is your example true.? $n=3$.? $\endgroup$– NosratiMar 4, 2017 at 11:11
-
$\begingroup$ yes, and also $n=4$ $\endgroup$– MclalalalaMar 4, 2017 at 11:12
1 Answer
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$.
-
-
$\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$ Mar 4, 2017 at 16:06
-
-
$\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$ 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$ Mar 4, 2017 at 16:16