Answer to Question #207592 in Discrete Mathematics for Aroosha ch

Question

• Use induction to prove for all n∈Nn∈N that n∑k=02k=2n+1−1.

Answer 1

Prove $\displaystyle\sum_{k=0}^n2^k=2^{n+1}-1$

Let $P(n)$ be the proposition that

$$2^0+2^1+2^2+...2^n=2^{n+1}-1$$

for the integer $n.$

BASIS STEP:

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

This completes the basis step.

INDUCTIVE STEP: For the inductive hypothesis, we assume that $P(k)$ is true for an arbitrary nonnegative integer $k.$ That is, we assume that

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

To carry out the inductive step using this assumption, we must show that when we assume that $P(k)$ is true, then $P(k+1)$ is also true. That is, we must show that

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

assuming the inductive hypothesis $P(k).$ Under the assumption of $P(k),$ we see that

$$2^0+2^1+2^2+...2^k+2^{k+1}$$

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

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

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

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

Note that we used the inductive hypothesis in the second equation in this string of equalities to replace $2^0+2^1+2^2+...2^k$ by $2^{k+1}-1.$ We have completed the inductive step.

Because we have completed the basis step and the inductive step, by mathematical induction we know that $P(n)$ is true for all nonnegative integers $n.$ That is,

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

for all nonnegative integers $n.$