Page 339 - Discrete Mathematics and Its Applications

318 5 / Induction and Recursion

EXAMPLE 3 Use mathematical induction to show that

n
2
1 + 2 + 2 + ··· + 2 = 2 n+1 − 1
for all nonnegative integers n.

2
n
Solution: Let P (n) be the proposition that 1 + 2 + 2 + ··· + 2 = 2 n+1 − 1 for the integer n.
1
0
BASIS STEP: P(0) is true because 2 = 1 = 2 − 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
k
2
1 + 2 + 2 + ··· + 2 = 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
k
1 + 2 + 2 + ··· + 2 + 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

k
2
k
2
1 + 2 + 2 + ··· + 2 + 2 k+1 = (1 + 2 + 2 + ··· + 2 ) + 2 k+1
IH k+1 k+1
= (2 − 1) + 2
= 2 · 2 k+1 − 1
= 2 k+2 − 1.
Note that we used the inductive hypothesis in the second equation in this string of equalities to
2
k
replace 1 + 2 + 2 + ··· + 2 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
n
we know that P (n) is true for all nonnegative integers n. That is, 1 + 2 + ··· + 2 = 2 n+1 − 1
for all nonnegative integers n. ▲
The formula given in Example 3 is a special case of a general result for the sum of terms
of a geometric progression (Theorem 1 in Section 2.4). We will use mathematical induction to
provide an alternative proof of this formula.
EXAMPLE 4 Sums of Geometric Progressions Use mathematical induction to prove this formula for the
sum of a finite number of terms of a geometric progression with initial term a and common
ratio r:

n n+1
ar − a
j 2 n
ar = a + ar + ar + ··· + ar = when r = 1,
r − 1
j = 0
where n is a nonnegative integer.

Solution: To prove this formula using mathematical induction, let P(n) be the statement that
the sum of the first n + 1 terms of a geometric progression in this formula is correct.
BASIS STEP: P(0) is true, because

ar 0+1 − a ar − a a(r − 1)
= = = a.
r − 1 r − 1 r − 1