Using induction with $\sum_{i=0}^{k-1}2^i=2^k-1$

Question

$\displaystyle\sum_{i=0}^{k-1}2^i=2^k-1$ for all $k \in\Bbb N$.

Clearly, the first step here is easy. You can start with k=1 and solve to get $2^0=2^1-1$.

What is a bit more challenging is the induction step. I don't even know where to begin here. Where would I even begin?

Answer 1

first prove that $\sum_{i=0}^{k}2^i = 2^{k+1}-1$

or equivalently $\sum_{i=0}^{k-1}2^i + 2^k= 2^k + 2^k - 1$

Answer 2

In the way your question is titled - you don't appear to be confident with sigma notation?

Sigma means "sum", so you may rephrase your question as a sum (i.e. physically write down the terms with ' ... ' to seperate the terms in between).

So $$\sum_{i=0}^{k-1} 2^i \text{ is equivalent to }2^0+2^1+2^2+\cdots2^{k-1} $$

Would this help you 'picture' the induction? It should be a very simple task! If you are not forced to use induction, simply observe that this is a geometric series, and immediately $$\sum_{i=0}^{k-1} 2^i = \frac{2^k-1}{2-1} = 2^k-1$$

For the induction itself:

BASE CASE: (you have already done this)

INDUCTIVE HYPOTHESIS: We assume that

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

and now we wish to show that if the hypothesis is true, then it is also true for $k+1$

$$\text{RTP: } \sum_{i=0}^{k}2^i=2^{k+1}-1$$

$$ LHS = \sum_{i=0}^{k}2^i = \sum_{i=0}^{k-1}2^i + 2^k = (2^k -1) + 2^k =2^{k+1}-1=RHS$$

and so we can conclude that the statement is true by induction.

If you found this answer useful, please accept it so it doesn't show up as an 'unanswered' question

Answer 3

You have stated a question, but are a bit ambiguous as to what your main concerns with the problem are. Is it the sigma that's confusing to you, or is it the induction? Nonetheless, let's try and clear those up.

Induction

Proof based on induction is a simple recursive proof that let's you extend a minimum of two cases to an infinite amount of cases. It merely requires your proof to be in terms of another case. This happens to be $n+1$ in most scenarios.

You start with a base case which you can rigorously show to be true. From there, you simply assume that a case, say $n$ is true, and then use that to show that the $n+1$ case is true.

Your Problem

For your particular problem, you have already identified the base case, $n = 1$.
From here, what you want to do is assume that $$\sum_{i=0}^{n} 2^{i} = 2^{n+1} - 1$$ (we call this the inductive hypothesis) and use that to prove that the $n+1$ case is true, or that $$\sum_{i=0}^{n+1} 2^{i} = 2^{n+2} - 1$$.

This may look daunting, but you can exploit the sigma here to rewrite $$\sum_{i=0}^{n+1} 2^{i} = \sum_{i=0}^{n} 2^{i} + 2^{n+1}$$ Now some of these terms should start looking familiar. Maybe one of them is our inductive hypothesis?

Try substituting in what we assumed to be true, and then make it look like $2^{n+2} - 1$. Best of luck.