Page 340 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 319

INDUCTIVE STEP: The inductive hypothesis is the statement that P(k) is true, where k is an
arbitrary nonnegative integer. That is, P(k) is the statement that

ar k+1 − a
2 k
a + ar + ar + ··· + ar = .
r − 1
To complete the inductive step we must show that if P(k) is true, then P(k + 1) is also true. To
show that this is the case, we first add ar k+1 to both sides of the equality asserted by P(k).We
find that

IH ar k+1 − a k+1
2
k+1
k
a + ar + ar + ··· + ar + ar = + ar .
r − 1
Rewriting the right-hand side of this equation shows that
ar k+1 − a k+1 ar k+1 − a ar k+2 − ar k+1
+ ar = +
r − 1 r − 1 r − 1
ar k+2 − a
= .
r − 1
Combining these last two equations gives

ar k+2 − a
2
k
k+1
a + ar + ar + ··· + ar + ar = .
r − 1
This shows that if the inductive hypothesis P(k) is true, then P(k + 1) must also be true. This
completes the inductive argument.
We have completed the basis step and the inductive step, so by mathematical induction P (n)
is true for all nonnegative integers n. This shows that the formula for the sum of the terms of a
geometric series is correct. ▲

As previously mentioned, the formula in Example 3 is the case of the formula in
Example 4 with a = 1 and r = 2. The reader should verify that putting these values for a
and r into the general formula gives the same formula as in Example 3.

PROVING INEQUALITIES Mathematical induction can be used to prove a variety of
inequalities that hold for all positive integers greater than a particular positive integer, as
Examples 5–7 illustrate.

EXAMPLE 5 Use mathematical induction to prove the inequality

n< 2 n

for all positive integers n.

n
Solution: Let P(n) be the proposition that n< 2 .
1
BASIS STEP: P(1) is true, because 1 < 2 = 2. This completes the basis step.
INDUCTIVE STEP: We first assume the inductive hypothesis that P(k) is true for anarbitrary
k
positiveintegerk.Thatis,theinductivehypothesisP(k)isthestatementthatk< 2 .Tocomplete
the inductive step, we need to show that if P(k) is true, then P(k + 1), which is the statement
k
that k + 1 < 2 k+1 , is true. That is, we need to show that if k< 2 , then k + 1 < 2 k+1 . To show