Page 343 - Discrete Mathematics and Its Applications

322 5 / Induction and Recursion

step, we must show that when we assume the inductive hypothesis, it follows that P(k + 1),
3
the statement that (k + 1) − (k + 1) is divisible by 3, is also true. That is, we must show that
3
(k + 1) − (k + 1) is divisible by 3. Note that
3
2
3
(k + 1) − (k + 1) = (k + 3k + 3k + 1) − (k + 1)
2
3
= (k − k) + 3(k + k).
3
Using the inductive hypothesis, we conclude that the first term k − k is divisible by 3. The
second term is divisible by 3 because it is 3 times an integer. So, by part (i) of Theorem 1 in
3
Section 4.1, we know that (k + 1) − (k + 1) is also divisible by 3. This completes the inductive
step.
Because we have completed both the basis step and the inductive step, by the prin-
3
ciple of mathematical induction we know that n − n is divisible by 3 whenever n is a
positive integer. ▲
The next example presents a more challenging proof by mathematical induction of a divis-
ibility result.
EXAMPLE 9 Use mathematical induction to prove that 7 n+2 + 8 2n+1 is divisible by 57 for every nonnegative
integer n.

Solution: To construct the proof, let P (n) denote the proposition: “7 n+2 + 8 2n+1 is divisible by
57.”
BASIS STEP: To complete the basis step, we must show that P(0) is true, because we want
to prove that P (n) is true for every nonnegative integer. We see that P(0) is true because
2
1
7 0+2 + 8 2·0+1 = 7 + 8 = 57 is divisible by 57. 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 7 k+2 + 8 2k+1 is divisible by 57. To complete the
inductive step, we must show that when we assume that the inductive hypothesis P(k) is true,
then P(k + 1), the statement that 7 (k+1)+2 + 8 2(k+1)+1 is divisible by 57, is also true.
The difficult part of the proof is to see how to use the inductive hypothesis. To take advantage
of the inductive hypothesis, we use these steps:

7 (k+1)+2 + 8 2(k+1)+1 = 7 k+3 + 8 2k+3
2
= 7 · 7 k+2 + 8 · 8 2k+1
= 7 · 7 k+2 + 64 · 8 2k+1
= 7(7 k+2 + 8 2k+1 ) + 57 · 8 2k+1 .

We can now use the inductive hypothesis, which states that 7 k+2 + 8 2k+1 is divisible by
57. We will use parts (i) and (ii) of Theorem 1 in Section 4.1. By part (ii) of this theorem, and
the inductive hypothesis, we conclude that the first term in this last sum, 7(7 k+2 + 8 2k+1 ),is
divisible by 57. By part (ii) of this theorem, the second term in this sum, 57 · 8 2k+1 , is divisible
by 57. Hence, by part (i) of this theorem, we conclude that 7(7 k+2 + 8 2k+1 ) + 57 · 8 2k+1 =
7 k+3 + 8 2k+3 is divisible by 57. This completes the inductive step.
Because we have completed both the basis step and the inductive step, by the principle of
mathematical induction we know that 7 n+2 + 8 2n+1 is divisible by 57 for every nonnegative
integer n. ▲

PROVING RESULTS ABOUT SETS Mathematical induction can be used to prove many
results about sets. In particular, in Example 10 we prove a formula for the number of subsets of
a finite set and in Example 11 we establish a set identity.