Page 341 - Discrete Mathematics and Its Applications

320 5 / Induction and Recursion

that this conditional statement is true for the positive integer k, we first add 1 to both sides of
k
k
k< 2 , and then note that 1 ≤ 2 . This tells us that
IH k k k k k+1
k + 1 < 2 + 1 ≤ 2 + 2 = 2 · 2 = 2 .
This shows that P(k + 1) is true, namely, that k + 1 < 2 k+1 , based on the assumption that P(k)
is true. The induction step is complete.
Therefore, because we have completed both the basis step and the inductive step, by
n
the principle of mathematical induction we have shown that n< 2 is true for all positive
integers n. ▲

n
EXAMPLE 6 Use mathematical induction to prove that 2 <n! for every integer n with n ≥ 4. (Note that this
inequality is false for n = 1, 2, and 3.)

n
Solution: Let P (n) be the proposition that 2 <n!.
BASIS STEP: To prove the inequality for n ≥ 4 requires that the basis step be P(4). Note that
4
P(4) is true, because 2 = 16 < 24 = 4!
INDUCTIVE STEP: For the inductive step, we assume that P(k) is true for an arbitrary integer k
k
with k ≥ 4. That is, we assume that 2 <k! for the positive integer k with k ≥ 4. We must show
k
that under this hypothesis, P(k + 1) is also true. That is, we must show that if 2 <k! for an
arbitrary positive integer k where k ≥ 4, then 2 k+1 <(k + 1)!.We have
2 k+1 = 2 · 2 k by definition of exponent

< 2 · k! by the inductive hypothesis
<(k + 1)k! because 2 <k + 1
= (k + 1)! by definition of factorial function.

This shows that P(k + 1) is true when P(k) is true. This completes the inductive step of the
proof.
We have completed the basis step and the inductive step. Hence, by mathematical induction
n
P (n) is true for all integers n with n ≥ 4. That is, we have proved that 2 <n! is true for all
integers n with n ≥ 4. ▲

An important inequality for the sum of the reciprocals of a set of positive integers will be
proved in Example 7.

EXAMPLE 7 An Inequality for Harmonic Numbers The harmonic numbers H j ,j = 1, 2, 3,..., are
defined by

1 1 1
H j = 1 + + + ··· + .
2 3 j
For instance,

1 1 1 25
H 4 = 1 + + + = .
2 3 4 12
Use mathematical induction to show that
n
H 2 ≥ 1 + ,
n
2
whenever n is a nonnegative integer.