Section 2.2 Induction
125
36. Prove that n! > n
3
for n ≥ 6.
37. Prove that n! > 2
n
for n ≥ 4.
38. Prove that n! > 3
n
for n ≥ 7.
39. Prove that n! ≥ 2
n−1
for n ≥ 1.
40. Prove that n! < n
n
for n ≥ 2.
41. Prove that (1 + x)
n
> 1 + x
n
for n > 1, x > 0.
42. Prove that a
a
b
b
n+1
< a
a
b
b
n
for n ≥ 1 and 0 < a < b.
43. Prove that 1 + 2 + c + n < n
2
for n > 1.
44. Prove that 1 +
1
4
+
1
9
+ c +
1
n
2 < 2 −
1
n
    for n ≥ 2
45. a. Try to use induction to prove that
1 +
1
2
+
1
4
+ c +
1
2
n < 2     for n ≥ 1
What goes wrong?
b. Prove that
1 +
1
2
+
1
4
+ c +
1
2
n = 2 −
1
2
n     for n ≥ 1
thus showing that
1 +
1
2
+
1
4
+ c +
1
2
n < 2     for n ≥ 1
46. Prove that
1 +
1
2
+
1
3
+ c +
1
2
n ≥ 1 +
n
2
    for n ≥ 1
(Note that the denominators increase by 1, not by powers of 2.)
For Exercises 47–58, prove that the statements are true for every positive integer.
47. 2
3n
− 1 is divisible by 7.
48. 3
2n
+ 7 is divisible by 8.
49. 7
n
− 2
n
is divisible by 5.
50. 13
n
− 6
n
is divisible by 7.
51. 2
n
+ (−1)
n+1
is divisible by 3.
52. 2
5n+1
+ 5
n+2
is divisible by 27.
53. 3
4n+2
+ 5
2n+1
is divisible by 14.
54. 7
2n
+ 16n − 1 is divisible by 64.
55. 10
n
+ 3 # 4
n+2
+ 5 is divisible by 9.
56. n
3
− n is divisible by 3.
57. n
3
+ 2n is divisible by 3.
58. x
n
− 1 is divisible by x − 1 for x ∙ 1.