3
$\begingroup$

Probably a lack of understanding of basic algebra. I can't get my head around why this sum to N equation simplifies to this much simpler form.

$$ \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i = 2^n - 2 $$

Background

To give you some background I am trying to derive $MaxInt(n) = 2^n-1$ which describes that the maximum integer which can be created using the two's complement where $n$ is the number of bits the integer is encoded by.

How two's complement encodes numbers with 4 bits is explained by the images below:

two's complement two's complement

Therefore: $$ MaxInt(n) = \sum_{i=0}^{n-2} 2^i = (2^0 + 2^1 + ... + 2^{n-3} + 2^{n-2} ) $$

Maybe there is a way of integrating this or simplifying it but I figured that this is a similar problem to sum to N where

$$ \frac{T(n) + T(n)}{2} = T(n) = \sum_{i=1}^{n} n-i+1 = \sum_{i=1}^{n} i $$

So following this logic $MaxInt(n)$ is also equal to:

$$ MaxInt(n) = \frac{MaxInt(n) + MaxInt(n)}{2} $$

Since

$$ (2^0 + 2^1 + ... + 2^{n-3} + 2^{n-2}) = (2^{n-2} + 2^{n-3} + ... 2^2 + 2^1 + 2^0) $$

Then

$$ MaxInt(n) = \sum_{i=0}^{n-2} 2^{n-2-i} = (2^{n-2} + 2^{n-3} + ... 2^2 + 2^1 + 2^0) $$

Putting it all together: $$ MaxInt(n) = \frac{\sum_{i=0}^{n-2} 2^{n-2-i} + \sum_{i=0}^{n-2} 2^i}{2} $$ $$ MaxInt(n) = \frac{\sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i}{2} $$

Which is when I got stuck, cheating with wolfrom alpha I found that

$$ \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i = 2^n - 2 $$

But I don't know why. If you see a better alternative way (i.e. not using sum to N method) of deriving $MaxInt(n) = 2^n-1$ please let me know.

Thanks for reading.

$\endgroup$
3
$\begingroup$

The thing you've asked to show isn't too hard: \begin{align} \sum_{i=0}^{n-2} \left(2^{-i+n-2} + 2^i\right) &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \sum_{i=0}^{n-2}\left(2^i\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(1 + 2 + \ldots + 2^{n-2}\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(2^{n-1} - 1\right) \\ \end{align} where that last thing comes form the formula for the sum of a geomtric series, which I think you probably know. Now let's simplify the left-hand term...

\begin{align} \sum_{i=0}^{n-2} \left(2^{-i+n-2} + 2^i\right) &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(2^{n-1} - 1\right) \\ &= \sum_{i=0}^{n-2} \left(2^{(n -2)-i)}\right) + \left(2^{n-1} - 1\right) \\ &= \left(2^{n -2} + 2^{n-3} + \ldots + 2^0\right) + \left(2^{n-1} - 1\right) \\ \end{align} which we recognize as another geometric series, written in reverse order; the sum there gives us \begin{align} \sum_{i=0}^{n-2} \left(2^{-i+n-2} + 2^i\right) &= \left(2^{n -2} + 2^{n-3} + \ldots + 2^0\right) + \left(2^{n-1} - 1\right) \\ &= \left(2^{n -1} - 1\right) + \left(2^{n-1} - 1\right) \\ &= 2 \cdot 2^{n -1} - 2 \\ &= 2^{n} - 2. \end{align}

Quick proof for the geometric series: If we expand $$ U = (1 - a) (1 + a + a^2 + \ldots a^k) $$ with the distributive law, and then gather like terms via the commutative law for addition, we get this: \begin{align} U &= (1 - a) (1 + a + a^2 + \ldots + a^{k-1} + a^k)\\ &= 1 \cdot (1 + a + a^2 + a^{k-1} + \ldots a^k) - a \cdot (1 + a + a^2 + \ldots + a^{k-1} + a^k)\\ &= (1 + a + a^2 + \ldots + a^{k-1} + a^k) - (a + a^2 + a^3 + \ldots + a^k + a^{k+1})\\ &= 1 + (a + a^2 + \ldots a^k) - (a + a^2 + a^3 + \ldots + a^k) - a^{k+1})\\ &= 1 - a^{k+1}) \end{align} so we have that $$ 1-a^{k+1} = (1-a) (1 + a + \ldots + a^k) $$ hence (for $a \ne 1$), $$ 1 + a + \ldots + a^k = \frac{1-a^{k+1}}{1-a}, $$ which is the formula for the sum of a finite geometric series whose ratio is not 1. For an infinite series whose ratio has absolute value less than 1, the infinite sum turns out to be $\frac{1}{1-a}$, by the way, but this requires a careful definition of a sum for an infinite series.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer. I guess what you have made me realize is I was looking for a proof of the geometric series. I have heard of / once learnt of this formula but I want to understand why it works ... $\endgroup$ Jun 13 '15 at 16:40
  • $\begingroup$ let $S_n= a + ar + ar^2+...+ar^{n-1}$. Then $rS_n = ar+ar^2+ar^3+...+ar^n$. Subtract one from the other, all the middle terms will cancel and after factorisation you get $S_n={a(1-r^n)\over 1-r}$ $\endgroup$
    – danimal
    Jun 13 '15 at 17:06
  • $\begingroup$ Thanks, danimal! I should have included that myself. $\endgroup$ Jun 13 '15 at 18:06
  • $\begingroup$ @JohnHughes, please could you include a small proof of geometric series in your answer so I can accept it $\endgroup$ Jun 15 '15 at 14:18
1
$\begingroup$

$$\large\begin{align} \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i &=\sum_{\begin{matrix}j\ +\ k\ =\ n-2\\ 0\;\le\; j,\ k\;\le\; n-2\end{matrix}}2^j+2^k\\\\ &=2\sum_{r=0}^{n-2}2^r\\ &=\sum_{r=1}^{n-1}2^r\\ &=\sum_{r=1}^{n-1}2^{r+1}-2^r\\ &=2^n-2\qquad\text{by telescoping}\quad \blacksquare \end{align}$$

$\endgroup$
1
$\begingroup$

First notice that for any $m$, $\sum_{i=0}^{m-1} 2^i = 2^m-1$. To see this (and really this is the geometric series proof applied to your situation), let $$S=\sum_{i=0}^{m-1} 2^i=1+2+4+8+\cdots+2^{m-1}.$$ Then \begin{eqnarray*} 2S&=&2+4+8+\cdots+2^{m-1}+2^m\\ &=& (-1+1)+2+4+\cdots+2^{m-1}+2^m\\&=& -1+(1+2+4+\cdots+2^{m-1})+2^m\\ &=& -1 + S + 2^m.\end{eqnarray*} So $2S=-1+S+2^m$ and so $S=2^m-1$.

Now your sum is $$\sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i = \sum_{i=0}^{n-2} 2^{(n-2)-i} + \sum_{i=0}^{n-2} 2^i.$$

But $$\sum_{i=0}^{n-2} 2^{(n-2)-i} = \sum_{i=0}^{n-2} 2^i.$$ Here, the left-side is the sum $2^{n-2}+2^{n-3}+\cdots + 2+1$ and the right-side just expresses this sum in the reverse order $1+2+\cdots+2^{n-3}+2^{n-2}$.

So putting this together you have \begin{eqnarray*} \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i &=& \sum_{i=0}^{n-2} 2^{(n-2)-i} + \sum_{i=0}^{n-2} 2^i\\ &=& \sum_{i=0}^{n-2} 2^{i} + \sum_{i=0}^{n-2} 2^i\\ &=&2\sum_{i=0}^{n-2} 2^i \\ &=& 2(2^{n-1}-1) \\ &=& 2^{n}-2\end{eqnarray*}

$\endgroup$
0
1
$\begingroup$

As, reversing the order, $$\sum_{i=0}^{n-2}2^{i-n+2}=\sum_{i=0}^{n-2}2^i$$ the global sum is $$2(2^{n-1}-1).$$

$\endgroup$
1
$\begingroup$

Applying the proof of the geometric series to this particular case:

$$ MaxInt(n) = S(n) = \sum_{i=0}^{n-2} 2^i = 2^0 + 2^1 ... + 2^{n-3} + 2^{n-2} $$

Adding up each term in the series:

$$ 2S(n) = (2^0 + 2^0) + (2^1 + 2^1) ... + (2^{n-3} + 2^{n-3}) + (2^{n-2} + 2^{n-2}) $$

Simplifying:

$$ 2S(n) = 2^1 + 2^2 ... + (2 \cdot \frac{2^{n}}{2^3}) + (2 \cdot \frac{2^{n}}{2^2}) $$

$$ 2S(n) = 2^1 + 2^2 ... + \frac{2^{n}}{2^2} + \frac{2^{n}}{2^1} $$

$$ 2S(n) = {\color{Blue} {2^1 + 2^2 ... + 2^{n-2}} } + 2^{n-1} $$

Notice what is in blue is actually $S(n)$ except it is missing the first term, lets call this part in blue $y$:

$$ 2S(n) = {\color{Blue} {y} } + 2^{n-1} $$

$$ {\color{Blue} {y} } = S(n) - 2^0 $$

Substituting in:

$$ 2S(n) = {\color{Blue} {S(n) -2^0} } + 2^{n-1} $$

$$ S(n) = 2^{n-1} - 2^0 $$

$$ = 2^{n-1} - 1 $$ $$ \therefore MaxInt(n) = \sum_{i=0}^{n-2} 2^i = 2^{n-1} - 1 $$

The above is the equation desired by the background question, but the original question asks for $2S(n)$

$$ 2S(n) = 2 \sum_{i=0}^{n-2} 2^i $$ $$ = 2^1 \cdot (2^{n-1} - 1 ) $$ $$ = 2^{n-1+1} - 2 $$ $$ = 2^{n} - 2 $$

$\endgroup$
2
  • $\begingroup$ You just forgot your exponent rules. $2S(n)=2^12^{n-1}-2= 2^{1+n-1}-2=2^n-2$ $\endgroup$
    – Casteels
    Jun 15 '15 at 7:49
  • $\begingroup$ ah yeah thanks! $\endgroup$ Jun 15 '15 at 13:26

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.