Answer to Question #347950 in Discrete Mathematics for Kaji

Question

Principle of mathematical induction to prove 1+2+2²+2³+....+2^n-1=2^n-1

Answer 1

Let $P(n)$ be the proposition that for the first $n$ positive integers

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

Basis Step:

$P(1)$is true, because $1=2^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

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

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

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

is also true.

$$1+2+2^2+2^3+...+2^{k-1}+2^{k+1-1}$$

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

$$=2^{k+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 positive integers $n.$ That is, we have proved that

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

for all positive integers $n.$