Page 342 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 321

n
Solution: To carry out the proof, let P (n) be the proposition that H 2 ≥ 1 + .
n
2
0
BASIS STEP: P(0) is true, because H 0 = H 1 = 1 ≥ 1 + .
2
2
INDUCTIVE STEP: The inductive hypothesis is the statement that P(k) is true, that is,
k
H k ≥ 1 + , where k is an arbitrary nonnegative integer. We must show that if P(k) is true,
2
2
k + 1
then P(k + 1), which states that H k+1 ≥ 1 + 2 , is also true. So, assuming the inductive
2
hypothesis, it follows that
1 1 1 1 1
H k+1 = 1 + + + ··· + + + ··· + by the definition of harmonic
2
k
2 3 2 k 2 + 1 2 k+1
number
1 1
k
= H k + + ··· + by the definition of 2 th harmonic
2
k
2 + 1 2 k+1 number

k 1 1
≥ 1 + + + ··· + by the inductive hypothesis
k
2 2 + 1 2 k+1

k k 1
k
≥ 1 + + 2 · because there are 2 terms
2 2 k+1 k+1
each ≥ 1/2
k 1

≥ 1 + + canceling a common factor of
2 2 k
2 in second term
k + 1
= 1 + .
2
This establishes the inductive step of the proof.
We have completed the basis step and the inductive step. Thus, by mathematical induction
n
P (n) is true for all nonnegative integers n. That is, the inequality H 2 ≥ 1 + for the harmonic
n
2
numbers holds for all nonnegative integers n. ▲
Remark: The inequality established here shows that the harmonic series
1 1 1
1 + + + ··· + + ···
2 3 n
is a divergent infinite series. This is an important example in the study of infinite series.
PROVING DIVISIBILITY RESULTS Mathematical induction can be used to prove divisibil-
ity results about integers. Although such results are often easier to prove using basic results in
number theory, it is instructive to see how to prove such results using mathematical induction,
as Examples 8 and 9 illustrate.
3
EXAMPLE 8 Use mathematical induction to prove that n − n is divisible by 3 whenever n is a posi-
tive integer. (Note that this is the statement with p = 3 of Fermat’s little theorem, which is
Theorem 3 of Section 4.4.)

3
Solution: To construct the proof, let P(n) denote the proposition: “n − n is divisible by 3.”
3
BASIS STEP: The statement P(1) is true because 1 − 1 = 0 is divisible by 3. This completes
the basis step.
INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) is true; that is, we
3
assume that k − k is divisible by 3 for an arbitrary positive integer k. To complete the inductive