Simplify $2^{(n-1)} + 2^{(n-2)} + .... + 2 + 1$ I know the answer is $2^n - 1$, but how to simplify it?
$\endgroup$ 18 Answers
$\begingroup$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$
$\endgroup$ $\begingroup$Observe that it is a Geometric Series with the first term $=2^{n-1}$ and common ratio $=\frac12$
$\endgroup$ 2 $\begingroup$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$
$\endgroup$ 3 $\begingroup$$$\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}$$
$\endgroup$ $\begingroup$$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$
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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).
$\endgroup$ $\begingroup$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$.
$\endgroup$
