Q:

induction help proving the sum of the n powers of 2

How do i prove using mathematical induction to prove that the sum of the firstn powers of 2 that can be computed by Evaluating function m(n) = $2^n -1$.
$\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = 2^n-1$
Should i substitute n = 1, k , k+1 in $2^n -1$ or $2^{n-1}$ ?
Please help me in finding it.

A:

Hint:
From 
$$\sum_{k=0}^{n-1}2^k=2^n-1$$ 
follow that
$$\sum_{k=0}^{n}2^k=\sum_{k=0}^{n-1}2^k+2^n=2^n-1+2^n=2\cdot2^n-1=2^{n+1}-1$$

A:

First of all, check the first case. The sum up to $n-1$ for $n=1$ should be:

$$\sum_{k=0}^{1-1}2^k=2^0= 2^1-1 \tag{wich is true}$$

Now, we must suppose that this is valid for any $n$:

$$\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = 2^n-1 \tag{suppose this is true}$$

Now, we must prove for $\color{blue}{n+1}$, and for do that, we gonna
try to find our supposition inside the expression for $n+1$:

$$\sum_{k=0}^{\color{Blue}{n+1}-1}2^k=\color{Green}{\underbrace{1+2+4+...+2^{n-1}}_{\text{our supposition}} }+ 2^{\color{Blue}{n+1}-1} = 2^{\color{Blue}{n+1}}-1$$
So, our supposition is inside the sum, we can, then, substitute it by the formula we supposed is true:
$$\sum_{k=0}^{\color{Blue}{n}}2^k=\color{Green}{2^n-1} + 2^{\color{Blue}{n}} = 2^{\color{Blue}{n+1}}-1$$
Now, we have two terms $2^n$, so we can group them in this form: $2*2^n = 2^{n+1}$, then:
$$\sum_{k=0}^{\color{Blue}{n}}2^k=2^{n+1}-1  = 2^{\color{Blue}{n+1}}-1$$
We proved that the middle part of the equation is equal to the last part, so now our proof by induction is complete.

