# Simplifying sum equation. (Solving max integer encoded by n bits)

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

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.

• 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 ... Jun 13 '15 at 16:40
• 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}$ Jun 13 '15 at 17:06
• Thanks, danimal! I should have included that myself. Jun 13 '15 at 18:06
• @JohnHughes, please could you include a small proof of geometric series in your answer so I can accept it Jun 15 '15 at 14:18

\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}

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*}

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

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

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