Page 400 - Discrete Mathematics and Its Applications

Supplementary Exercises 379

Supplementary Exercises

2

1. Use mathematical induction to show that 2 3 + 2 9 + 27 + uct rule and the fact that f (x) = e x to prove that
2 1 (n) x
··· + n = 1 − n whenever n is a positive integer. g (x) = (x + n)e whenever n is a positive integer.
3 3
3 3 3 x
2. Use mathematical induction to show that 1 + 3 + 5 + 18. (Requires calculus) Suppose that f(x) = e and g(x) =
cx
2
3
2
··· + (2n + 1) = (n + 1) (2n + 4n + 1) whenever n e , where c is a constant. Use mathematical induction to-
x

is a positive integer. gether with the chain rule and the fact that f (x) = e to
n cx
0 1 prove that g (n) = c e whenever n is a positive integer.
3. Use mathematical induction to show that 1 · 2 + 2 · 2 +
2
n
3 · 2 + ··· + n · 2 n−1 = (n − 1) · 2 + 1 whenever n is ∗ 19. Formulate a conjecture about which Fibonacci numbers
a positive integer. are even, and use a form of mathematical induction to
prove your conjecture.
4. Use mathematical induction to show that
∗ 20. Determine which Fibonacci numbers are divisible by 3.
1 1 1 n
+ + ··· + = Use a form of mathematical induction to prove your con-
1 · 3 3 · 5 (2n − 1)(2n + 1) 2n + 1
jecture.
whenever n is a positive integer. ∗ 21. Prove that f k f n + f k+1 f n+1 = f n+k+1 for all nonnega-
5. Show that tive integers n and k, where f i denotes the ith Fibonacci
1 1 1 n number.
+ + ··· + =
1 · 4 4 · 7 (3n − 2)(3n + 1) 3n + 1 Recall from Example 15 of Section 2.4 that the sequence
of Lucas numbers is defined by l 0 = 2, l 1 = 1, and l n =
whenever n is a positive integer.
l n−1 + l n−2 for n = 2, 3, 4,....
n
2
6. Use mathematical induction to show that 2 >n + n
whenever n is an integer greater than 4. 22. Show that f n + f n+2 = l n+1 whenever n is a positive in-
3
n
7. Use mathematical induction to show that 2 >n when- teger, where f i and l i are the ith Fibonacci number and
ith Lucas number, respectively.
ever n is an integer greater than 9. 2 2 2
23. Show that l + l + ··· + l = l n l n+1 + 2 whenever n is
n
4
n
8. Find an integer N such that 2 >n whenever n is greater 0 1
a nonnegative integer and l i is the ith Lucas number.
than N. Prove that your result is correct using mathemat-
∗
ical induction. 24. Use mathematical induction to show that the product of
any n consecutive positive integers is divisible by n!.
9. Use mathematical induction to prove that a − b is a factor
n
n
of a − b whenever n is a positive integer. [Hint: Use the identity m(m + 1) ··· (m + n −
1)/n!= (m − 1)m(m + 1) ··· (m + n − 2)/n!+
3
10. Use mathematical induction to prove that 9 divides n + m(m+ 1) ··· (m + n − 2)/(n − 1)!.]
3
3
(n + 1) + (n + 2) whenever n is a nonnegative integer.
25. Use mathematical induction to show that (cos x +
11. Use mathematical induction to prove that 43 divides i sin x) = cos nx + i sin nx whenever n is a positive in-
n
6 n+1 + 7 2n−1 for every positive integer n.
teger. (Here i is the square root of −1.) [Hint: Use
12. Use mathematical induction to prove that 64 divides the identities cos(a + b) = cos a cos b − sin a sin b and
3 2n+2 + 56n + 55 for every positive integer n. sin(a + b) = sin a cos b + cos a sin b.]
13. Use mathematical induction to prove this formula for the ∗ 26. Use mathematical induction to show that n cos jx =
j=1
sum of the terms of an arithmetic progression. cos[(n + 1)x/2] sin(nx/2)/ sin(x/2) whenever n is a
positive integer and sin(x/2) = 0.
a + (a + d) + ··· + (a + nd) =
2 j
(n + 1)(2a + nd)/2 27. Use mathematical induction to prove that n j 2 =
j=1
2 n+1
n 2 − n2 n+2 + 3 · 2 n+1 − 6 for every positive inte-
14. Suppose that a j ≡ b j (mod m) for j = 1, 2,...,n. Use ger n.
mathematical induction to prove that
28. (Requires calculus) Suppose that the sequence
a) n a j ≡ n b j (mod m). x 1 ,x 2 ,...,x n ,... is recursively defined by x 1 = 0 and
j = 1 j = 1 √
x n+1 = x n + 6.
b) n a j ≡ n b j (mod m). a) Use mathematical induction to show that x 1 <x 2 <
j = 1 j = 1 ··· <x n < ··· , that is, the sequence {x n } is monoton-
15. Show that if n is a positive integer, then ically increasing.
b) Use mathematical induction to prove that x n < 3 for
k + 4 n(3n + 7)
n
k = 1 = . n = 1, 2,....
k(k + 1)(k + 2) 2(n + 1)(n + 2)
c) Show that lim n→∞ x n = 3.
2
16. For which positive integers n is n + 6 <(n − 8n)/16? 29. Show if n is a positive integer with n ≥ 2, then
Prove your answer using mathematical induction.
n
x 1 (n − 1)(3n + 2)
17. (Requires calculus) Suppose that f(x) = e and g(x) = 2 =
x
xe . Use mathematical induction together with the prod- j=2 j − 1 4n(n + 1).