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

Question

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!

Answer 1

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.

Answer 2

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