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.
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$$
$$\sum_{k=0}^{1-1}2^k=2^0= 2^1-1 \tag{wich is true}$$
$$\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = 2^n-1 \tag{suppose this is true}$$
$$\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.
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.
