Answer to Question #300617 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

a)

i)

$$b_0=1, b_1=2, b_n=2^n$$

Let $a_1=b_0=1, a_2=b_1=2, ..., a_{n+1}=b_n=2^n$

We have the geometric progression with the $a=1$ and the common ratio $r=2.$

$$\displaystyle\sum_{i=0}^{n}2^i=S_{n+1}=\displaystyle\sum_{j=1}^{n+1}a_j=\dfrac{a(1-r^{n+1})}{1-r}$$

$$=\dfrac{1(1-2^{n+1})}{1-2}=2^{n+1}-1$$

ii) Let $P(n)$ be the proposition that the sum $\displaystyle\sum_{i=0}^{n}2^i$ is $2^{n+1}-1.$

Basis Step

$P(0)$ is true because $2^0=1=2^{0+1}-1.$

Inductive Step

For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary positive integer $k.$ That is, we assume that

$$\displaystyle\sum_{i=0}^{k}2^i=1+2+4+...+2^k=2^{k+1}-1$$

Under this assumption, it must be shown that $P(k + 1)$ is true, namely, that

$$1+2+4+...+2^k+2^{k+1}=2^{(k+1)+1}-1$$

is also true.

When we add $2^{k+1}$ to both sides of the equation in $P(k),$ we obtain

$$1+2+4+...+2^k+2^{k+1}=2^{k+1}-1+2^{k+1}$$

$$=2\cdot2^{k+1}-1$$

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

This last equation shows that $P(k + 1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all integers $n\ge0$ . That is, we have proven that

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