0
$\begingroup$

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.

$\endgroup$

3 Answers 3

3
$\begingroup$
  • 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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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