2
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ What happens if you add $1$? $\endgroup$ – Gottfried Helms Dec 3 '13 at 10:35
8
$\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$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ to the Downvoter, please pinpoint the mistake $\endgroup$ – lab bhattacharjee Dec 3 '13 at 10:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel R Dec 3 '13 at 10:56
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$
  • $\begingroup$ This is possible only when $x\ne1$, just to be clear. $\endgroup$ – egreg Dec 3 '13 at 10:17
  • $\begingroup$ thanks for reminding me i forgot to mention that. when x =1the sum is trivial. $\endgroup$ – toufik_kh.17 Dec 3 '13 at 10:19
  • $\begingroup$ now it is mentioned in the first line. $\endgroup$ – toufik_kh.17 Dec 3 '13 at 10:26
1
$\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$
1
$\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$
1
$\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$
0
$\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$
0
$\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$

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.