Page 351 - Discrete Mathematics and Its Applications

330 5 / Induction and Recursion

9. a) Find a formula for the sum of the first n even positive c) What is the inductive hypothesis?
integers. d) What do you need to prove in the inductive step?
b) Prove the formula that you conjectured in part (a). e) Complete the inductive step.
10. a) Find a formula for f) Explain why these steps show that this inequality is
true whenever n is an integer greater than 1.
1 1 1
n
+ + ··· + 20. Prove that 3 <n! if n is an integer greater than 6.
1 · 2 2 · 3 n(n + 1) n 2
21. Prove that 2 >n if n is an integer greater than 4.
by examining the values of this expression for small 22. For which nonnegative integers n is n ≤ n!? Prove your
2
values of n. answer.
b) Prove the formula you conjectured in part (a). n
23. For which nonnegative integers n is 2n + 3 ≤ 2 ? Prove
11. a) Find a formula for
your answer.
1 1 1 1 24. Prove that 1/(2n) ≤[1 · 3 · 5 · ··· · (2n − 1)]/(2 · 4 ·
+ + + ··· +
2 4 8 2 n ··· · 2n) whenever n is a positive integer.
n
by examining the values of this expression for small ∗ 25. Prove that if h> −1, then 1 + nh ≤ (1 + h) for all non-
values of n. negative integers n. This is called Bernoulli’s inequality.
b) Prove the formula you conjectured in part (a).
12. Prove that ∗ 26. Suppose that a and b are real numbers with 0 <b <a.
n n
n j n+1 n Prove that if n is a positive integer, then a − b ≤
1 2 + (−1) n−1
− = na (a − b).
2 3 · 2 n ∗
j=0 27. Prove that for every positive integer n,
whenever n is a nonnegative integer. 1 1 1 √
1 + √ + √ + ··· + √ > 2( n + 1 − 1).
2
2
2
13. Prove that 1 − 2 + 3 − ··· + (−1) n−1 2 n−1 2 3 n
n = (−1)
n(n + 1)/2 whenever n is a positive integer. 2
n k 28. Prove that n − 7n + 12 is nonnegative whenever n is an
14. Prove that for every positive integer n, k = 1 k2 = integer with n ≥ 3.
(n − 1)2 n+1 + 2.
In Exercises 29 and 30, H n denotes the nth harmonic number.
15. Prove that for every positive integer n,
∗ 29. Prove that H 2 ≤ 1 + n whenever n is a nonnegative in-
n
1 · 2 + 2 · 3 + ··· + n(n + 1) = n(n + 1)(n + 2)/3. teger.
∗ 30. Prove that
16. Prove that for every positive integer n,
H 1 + H 2 + ··· + H n = (n + 1)H n − n.
1 · 2 · 3 + 2 · 3 · 4 + ··· + n(n + 1)(n + 2)
= n(n + 1)(n + 2)(n + 3)/4. Use mathematical induction in Exercises 31–37 to prove di-
visibility facts.
n 4 2 2
17. Provethat j = 1 j = n(n + 1)(2n + 1)(3n + 3n −1)/30 31. Prove that 2 divides n + n whenever n is a positive in-
whenever n is a positive integer. teger.
3
Use mathematical induction to prove the inequalities in Exer- 32. Prove that 3 divides n + 2n whenever n is a positive
cises 18–30. integer.
n
5
18. Let P(n) be the statement that n! <n , where n is an 33. Prove that 5 divides n − n whenever n is a nonnegative
integer greater than 1. integer.
3
a) What is the statement P(2)? 34. Prove that 6 divides n − n whenever n is a nonnegative
b) Show that P(2) is true, completing the basis step of integer.
the proof. ∗ 35. Prove that n − 1 is divisible by 8 whenever n is an odd
2
c) What is the inductive hypothesis? positive integer.
d) What do you need to prove in the inductive step? ∗ 36. Prove that 21 divides 4 n+1 + 5 2n−1 whenever n is a pos-
e) Complete the inductive step. itive integer.
f) Explain why these steps show that this inequality is
∗ 37. Prove that if n is a positive integer, then 133 divides
true whenever n is an integer greater than 1. n+1 2n−1
11 + 12 .
19. Let P(n) be the statement that
Use mathematical induction in Exercises 38–46 to prove re-
1 1 1 1 sults about sets.
1 + + + ··· + 2 < 2 − ,
4 9 n n 38. Prove that if A 1 ,A 2 ,...,A n and B 1 ,B 2 ,...,B n are sets
where n is an integer greater than 1. such that A j ⊆ B j for j = 1, 2,...,n, then
a) What is the statement P(2)? n n

b) Show that P(2) is true, completing the basis step of A j ⊆ B j .
the proof. j = 1 j = 1