Answer to Question #300283 in Discrete Mathematics for Snave

Question

Prove that \sum_{i=0}^{n} 2^{i} = 2^{n + 1} - 1 Use mathematical induction for this proof and discuss/explain each step.

Answer 1

Let us prove that $\sum\limits_{i=0}^{n} 2^{i} = 2^{n + 1} - 1$ using mathematical induction.

For $n=1,$ we have that the left side is $2^0+2^1=3,$ and the right side is $2^2-1=3.$ Therefore, for $n=1$ the equality is true.

Suppose that the equality is true for $n=k,$ that is $\sum\limits_{i=0}^{k} 2^{i} = 2^{k + 1} - 1.$

Let us prove for $n=k+1.$

It follows that

$\sum\limits_{i=0}^{k+1} 2^{i} =\sum\limits_{i=0}^{k} 2^{i}+2^{k+1} = 2^{k + 1}-1+ 2^{k + 1} =2\cdot 2^{k + 1} - 1=2^{k+2}-1.$

We conclude that by principle of mathematical induction the statement is true for all natural numbers $n.$