# Using induction to prove $\sum_{k=0}^{N-1} 2^k = 2^N-1$

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!

• Note that your "$(r+1)$-th term" is $2^r$.
– MSDG
May 4 '19 at 20:13
• Ahhhh thank you :)
– user635953
May 4 '19 at 20:17
• 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.
– zwim
May 4 '19 at 21:07

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

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

• Ahhhh thank you! Understood now, greatly appreciated :)
– user635953
May 4 '19 at 20:17

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