Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

Question

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$

Answer 1

Step 1: For $n=1$, the LHS is $2^1-1=1$, while the RHS is $\sum_{i=0}^0 2^i=0$, which are equal.

Step 2: Assume that $2^n-1=\sum_{i=0}^{n-1}2^i$ holds, and try to use this fact to prove that $2^{n+1}-1=\sum_{i=0}^n2^i$.

Answer 2

For $n\geq 1$, let $S(n)$ denote the statement $$ S(n) : \sum_{i=0} ^{n-1} 2^i=2^n-1. $$ Base case ($n=1$): $S(1)$ says that $\sum_{i=0}^{1-1}2^i = 2^0=1=2^1-1$, and this is true.

Inductive step: Fix some $k\geq 1$ and assume that $S(k)$ is true where $$ S(k) : \sum_{i=0} ^{k-1} 2^i=2^k-1. $$ To be shown is that $S(k+1)$ follows where $$ S(k+1) : \sum_{i=0} ^{k} 2^i=2^{k+1}-1 $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} \sum_{i=0}^k 2^i &= 2^k+\sum_{i=0}^{k-1}2^i\tag{by defn. of $\Sigma$}\\[0.5em] &= 2^k+(2^k-1)\tag{by induction hypothesis}\\[0.5em] &= 2\cdot 2^k-1\tag{simplify}\\[0.5em] &=2^{k+1}-1,\tag{desired expression} \end{align} we end up at the right-hand side of $S(k+1)$, thus completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$.

Answer 3

We need to prove it for n=1. $$2^1-1=1=2^0=\sum_{i=0}^{1}2^i$$ Now we suppose it valid for $n=k$

We prove it for $n=k+1$ $$\sum_{i=0}^{k+1}2^i=\sum_{i=1}^{k+1}2^i+1=\sum_{i=1}^{k+1}2^i+2-1=2(\sum_{i=0}^{k}2^i+1)-1=2((2^k-1)+1)-1=2^{k+1}-1$$

Answer 4

Detailed/slightly rigourous proof:

We have to prove that the set $$S = \{k\in \mathbb{N} : 2^k -1 = \sum_{i=0}^{k-1} 2^i \} = \mathbb{N}.$$ In order to do that, we prove that $ S \subset \mathbb{N}$ and $\mathbb{N} \subset S$, so that we get $S = \mathbb{N}$.

First part: $S \subset \mathbb{N}$:

By definition of the set S, it is clear that $S \subset \mathbb{N}$, because $k \in S \Rightarrow k \in \mathbb{N}. \,\,\,\,\,\square$

Second part: $\mathbb{N} \subset S$.

We will show that $k \in \mathbb{N} \Rightarrow k \in S$.

To do that, we prove $1 \in S$, and $j \in S \Rightarrow j+1 \in S$.

• $1 \in S$:

$2^1 - 1 = 1$ and $1 \in \mathbb{N}$ leads to $1 \in S$

• $j \in S \Rightarrow j+1 \in S$

Our hypothesis is that $j \in S$, and we have to show that, if the hypothesis is true, then the conclusion is also true. Note that we are not showing that the hypothesis IS true, we are only showing that the hypothesis GUARANTEES the conclusion (this confused me a lot when i was learning induction).

Proceeding, this step is usually called the induction step: Starting with $j \in S$, we have the (assumed true) proposition: $$ 2^{j} - 1 = \sum_{i=0}^{j-1}2^i$$

By definition of summation, we can write:

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

However, since we are assuming for the sake of argument that $ 2^{j} - 1 = \sum_{i=0}^{j-1}2^i$ then we can substitute in $2^{j}- 1$ in the formula that we have just arrived at, leading to:

$$ \sum_{i=0}^{j}2^i = (2^j -1)+ 2^{j}$$

Which we can simplify to give:

$$ \sum_{i=0}^{j}2^i = 2(2^j) -1 = 2^{j+1} -1.$$

So we have shown that $ j \in S \Rightarrow j+1 \in S$.

Hence, if an element $b \in \mathbb{N}$, then $b \in \mathbb{s}. \,\,\,\,\,\,$

This completes our proof. $\square$