induction help proving the sum of the n powers of 2

Question

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.

Answer 1

• 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.

Answer 2

First prove the base case: That

$\sum_0^{1-1} 2^k=2^1-1$.

Then , assuming that

$\sum_0^{n-1}2^k=2^n-1$ is true,

that $\sum_0^{(n+1)-1}2^k=2^{n+1}-1$ is true.

Answer 3

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