3
$\begingroup$

I have this summation and I was attempting to prove it by induction however I have gotten stuck and not sure how to carry on further, if anyone could help point me in the right way that would be much appreciated! $$\sum_{k=0}^{N-1} 2^k = 2^N-1$$

So first I have the base case: $n=2$:

$$\sum_{k=0}^{1} 2^k = 3, \iff 2^2-1=3$$

Then I assumed true for $n=r$ so: $$\sum_{k=0}^{r-1} 2^k = 2^r-1$$

Then I considered $n=r+1$ so I want to show: $$\sum_{k=0}^{r} 2^k = 2^{r+1}-1$$

$$\sum_{k=0}^{r} 2^k = \sum_{k=0}^{r-1} 2^k + (r+1)^\mathrm{th}\text{ term}$$ $$\sum_{k=0}^{r} 2^k = 2^r -1+ (2^{r+1}-1)$$

But now I'm not sure how to go further or whether I got the "$(r+1)^{th}$" term correct or if I can even do this? If anyone can help me complete it and give me tips on induction as I always fail on the inductive step!

$\endgroup$
3
  • 3
    $\begingroup$ Note that your "$(r+1)$-th term" is $2^r$. $\endgroup$
    – MSDG
    May 4 '19 at 20:13
  • $\begingroup$ Ahhhh thank you :) $\endgroup$
    – user635953
    May 4 '19 at 20:17
  • $\begingroup$ Note that naming the sum can help, since $S_r=2S_{r-1}+1$ now if $S_{r-1}=2^r-1$ then $S_r=2(2^r-1)+1=2^{r+1}-1$. The sum symbol and index stuff do not come in the way of your thinking. $\endgroup$
    – zwim
    May 4 '19 at 21:07
1
$\begingroup$

You made a minor mistake in your induction: you're not pulling out the $(r+1)^{th}$ term. Well, you are, if you count from $0$, but the summand you're pulling out is meant to correspond to the final index, where the index is $k=r$. (You took the $k=r+1$ term out instead.) That is,

$$\sum_{k=0}^r 2^k = 2^r + \sum_{k=0}^{r-1} 2^k$$

By your induction hypothesis then

$$2^r + \sum_{k=0}^{r-1} 2^k = 2^r + 2^r - 1 = 2(2^r) - 1 = 2^{r+1} - 1$$

which is what you sought to prove in your induction step.

$\endgroup$
1
  • 1
    $\begingroup$ Ahhhh thank you! Understood now, greatly appreciated :) $\endgroup$
    – user635953
    May 4 '19 at 20:17
0
$\begingroup$

You assume:

$$\sum_{k=0}^{r-1}2^k=2^r-1$$ Then, it follows:

$$\sum_{k=0}^r2^k=(2^r-1)+2^r=2(2^r)-1=2^{r+1}-1$$

$\endgroup$

Your Answer

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