Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am attempting to prove using induction:

$\sum_0^n 2i = 2^{n + 1} - 1$

I have gotten to the point where I need to show:

$2^{n+1} + 2n + 1 = 2^{n+2} - 1$

How do I prove this? Or should I be proving the initial question a different way

share|improve this question
4  
$13= 2^{2+1}+ 2\cdot 2+1\neq 2^{2+2}-1=15$. –  O.L. Oct 5 '13 at 4:03
1  
For intuition, $2^{n+2}$ is twice as big as $2^{n+1}$ No way $2n$ can get close for large $n$. –  Ross Millikan Oct 5 '13 at 4:06
    
Whenever it's true, you can "prove" that $1 \to \infty$ since $\displaystyle{{2^{n} \over n} = 1 + {1 \over n}}$. –  Felix Marin Oct 5 '13 at 6:04

2 Answers 2

up vote 5 down vote accepted

You missed the power of $2$ in the Left hand side

and the range of $i$ should start from $0$ instead of $1$

We find $\displaystyle\sum_0^1 2^i =1+2=3 $ and $ 2^{1 + 1} - 1=4-1=3$

So, $\displaystyle\sum_0^n 2^i = 2^{n + 1} - 1$ is true for $n=1$

Let $\displaystyle\sum_0^n 2^i = 2^{n + 1} - 1$ is true for $n=m$

$$\implies \sum_0^m 2^i = 2^{m + 1} - 1$$

$$\implies \sum_0^{m+1}2^i =\sum_0^m 2^i +2^{m+1}= 2^{m + 1} - 1 +2^{m+1}=2^{m+1}(1+1)-1=2^{m+2}-1$$

share|improve this answer
    
Ah, that makes a lot more sense. I copied the problem down incorrectly - thanks very much! –  sdasdadas Oct 5 '13 at 4:24
1  
@sdasdadas, my pleasure. In induction,always validate the base case first –  lab bhattacharjee Oct 5 '13 at 4:40

Note that $2^{n+2}-2^{n+1}=2^{n+1}$. Then we have that $2n+1=2^{n+1}-1$. So $2(n+1)=2^{n+1}$. Then $0=2^{n}-n-1$. So if $n \in \mathbb{Z}$, then your statement is only true for $n \in \{0,1\}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.