# Simplify $2^{(n-1)} + 2^{(n-2)} + … + 2 + 1$

Simplify $2^{(n-1)} + 2^{(n-2)} + .... + 2 + 1$ I know the answer is $2^n - 1$, but how to simplify it?

• What happens if you add $1$? – Gottfried Helms Dec 3 '13 at 10:35

First way:

$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+a^2b^{n-3}+ab^{n-2}+b^{n-1})$

set a=2, b=1

Edit: Second way.

Set $X=2^{(n-1)} + 2^{(n-2)} + … + 2 + 1$

$2X=2^n+2^{(n-1)} + 2^{(n-2)} + … + 2$

$2X=2^n+2^{(n-1)} + 2^{(n-2)} + … + 2 +1 -1$

$2X=2^n+X-1$

$X=2^n-1$

Observe that it is a Geometric Series with the first term $=2^{n-1}$ and common ratio $=\frac12$

• to the Downvoter, please pinpoint the mistake – lab bhattacharjee Dec 3 '13 at 10:37
• Someone seems to have downvoted all the answers, and is possibly out on a downvoting spree also on other questions. I've flagged this for moderator attention. – Daniel R Dec 3 '13 at 10:56

let $S= 1+x+x^2+.......+x^{n-1}$ where $x\ne1$

Multiply this equation by $x$ on both sides and get:

$xS= x+x^2+...........+x^{n}$

now subtract the second equality from the first one and you will end up with:

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

simplify:

$(1-x)S=1-x^n$ which implies that $S=\frac{1-x^n}{1-x}$

when $x=2$; $S=\frac{1-2^n}{1-2}=2^n-1$

• This is possible only when $x\ne1$, just to be clear. – egreg Dec 3 '13 at 10:17
• thanks for reminding me i forgot to mention that. when x =1the sum is trivial. – toufik_kh.17 Dec 3 '13 at 10:19
• now it is mentioned in the first line. – toufik_kh.17 Dec 3 '13 at 10:26

$$\begin{eqnarray} \\ \text{Let } 2^{(n-1)} + 2^{(n-2)} + \cdots + 2 + 1 &=& S \\ 2^{n} + 2^{(n-1)} + .... + 2^2 + 2 &=& 2S \tag {multiply both sides by 2} \\ 2^{n} + 2^{(n-1)} + .... + 2^2 + 2 +1 &=& 2S +1\tag {add 1 to both sides } \\ 2^{n} + S &=& 2S +1\tag {replace the term on LHS by S } \\ 2^{n} &=& S +1\tag {subtract S from both sides } \\ 2^{n} -1 &=& S \\ S &=& 2^{n} -1 \quad \square \end{eqnarray}$$

$2^{n-1}+\cdots+2^{0}=\left(2-1\right)\left(2^{n-1}+\cdots+2^{0}\right)=\left(2^{n}+\cdots+2^{1}\right)-\left(2^{n-1}+\cdots+2^{0}\right)=2^{n}-1$

Forget about all the smart generic formulas. Just rewrite the last summand $1$ as $2-1$. You get $$2^{n-1} + 2^{n-2} + \ldots + 2^3 + 2^2 + 2 + 2 - 1.$$ Now group the $2$'s together. $2 + 2 = 2^2$, so you get $$2^{n-1} + 2^{n-2} + \ldots + 2^3 + 2^2 + 2^2 - 1$$ Now group $2^2$ and $2^2$ together to get $2^2 + 2^2 = 2^3$: $$2^{n-1} + 2^{n-2} + \ldots + 2^3 + 2^3 - 1$$ If you go on in this fashion, you will eventually come to $2^n - 1$. The actual number of steps in this process depends on $n$, so technically this should be framed as a proof by induction.

Another "proof" (this was actually the way I had "proved" it myself until I saw the GP proof):

The first summand is 1 followed by a $n-1$ in base 2. The later ones are with one less zero every time. Adding them up results in a number composed of 1 followed by n-1 zeros, which is $2^n-1$ (1 followed by n zeros minus one).

This can be done by induction. The goal is to show that for all $n \ge 0$, $\sum_{i=0}^n 2^i = 2^{n+1}$

First consider the base case $n=0$. This checks out because $2^0 = 1 = 2^1 -1$

Now $\sum_{i=0}^n 2^i = 2^n + \sum_{i=0}^{n-1} 2^i = 2^n +2^n -1 = 2*2^n -1 =2^{n+1} -1$.