5 Example 2

Let's try to prove that $\forall k \in I: (k > 0) \rightarrow (2^k = 1+\sum_{i = 0}^{k-1} 2^i)$. In other words, $2^k = 1+(1 + 2 + 4 + 8 + \cdots 2^{k-1})$ for all $k > 0$.

The base case is simple (when $k = 1$): $2^1 = 2^0+1 = 1+1 = 2$.

The induction step states that $\forall k \in I: (k > 0 \wedge 2^k = 1+\sum_{i=0}^{k-1} 2^i) \rightarrow (2^{k+1} = 1+\sum_{i=0}^{k} 2^i)$. We need to assert this proposition:

$$2^{k+1} = 2(2^k)$$ (5)

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

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

$$= 2 + \sum_{i=1}^k 2^i$$ (8)

$$= 1 + (1+\sum_{i=1}^k 2^i)$$ (9)

$$= 1 + \sum_{i=0}^k 2^i$$ (10)

Because we proved the base case and also the induction step, we conclude that the original proposition is true.