# How do I prove $2^{n+1} + 2n + 1 = 2^{n+2} - 1$

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

-
$13= 2^{2+1}+ 2\cdot 2+1\neq 2^{2+2}-1=15$. –  O.L. Oct 5 '13 at 4:03
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

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

-
Ah, that makes a lot more sense. I copied the problem down incorrectly - thanks very much! –  sdasdadas Oct 5 '13 at 4:24
@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\}$.

-