Page 546 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 525

a) Find a recurrence relation for {L n }, where L n is the 23. Consider the nonhomogeneous linear recurrence relation
n
number of lobsters caught in year n, under the as- a n = 3a n−1 + 2 .
sumption for this model. a) Show that a n =−2 n+1 is a solution of this recurrence
b) Find L n if 100,000 lobsters were caught in year 1 and relation.
300,000 were caught in year 2. b) Use Theorem 5 to find all solutions of this recurrence
9. A deposit of $100,000 is made to an investment fund at relation.
the beginning of a year. On the last day of each year two c) Find the solution with a 0 = 1.
dividends are awarded. The first dividend is 20% of the 24. Consider the nonhomogeneous linear recurrence relation
amount in the account during that year. The second divi- a n = 2a n−1 + 2 .
n
dend is 45% of the amount in the account in the previous a) Show that a n = n2 is a solution of this recurrence
n
year. relation.
a) Find a recurrence relation for {P n }, where P n is the b) Use Theorem 5 to find all solutions of this recurrence
amountintheaccountattheendof nyearsifnomoney relation.
is ever withdrawn. c) Find the solution with a 0 = 2.
b) How much is in the account after n years if no money 25. a) Determine values of the constants A and B such
has been withdrawn? that a n = An + B is a solution of recurrence relation
∗ 10. Prove Theorem 2. a n = 2a n−1 + n + 5.
11. The Lucas numbers satisfy the recurrence relation b) Use Theorem 5 to find all solutions of this recurrence
relation.
L n = L n−1 + L n−2 , c) Find the solution of this recurrence relation with
a 0 = 4.
and the initial conditions L 0 = 2 and L 1 = 1.
26. What is the general form of the particular so-
a) Show that L n = f n−1 + f n+1 for n = 2, 3,...,
where f n is the nth Fibonacci number. lution guaranteed to exist by Theorem 6 of
the linear nonhomogeneous recurrence relation
b) Find an explicit formula for the Lucas numbers.
a n = 6a n−1 − 12a n−2 + 8a n−3 + F(n) if
12. Find the solution to a n = 2a n−1 + a n−2 − 2a n−3 a) F(n) = n ? b) F(n) = 2 ?
n
2
for n = 3, 4, 5,..., with a 0 = 3, a 1 = 6, and a 2 = 0. n n
c) F(n) = n2 ? d) F(n) = (−2) ?
13. Find the solution to a n = 7a n−2 + 6a n−3 with a 0 = 9, e) F(n) = n 2 ? f) F(n) = n (−2) ?
3
2 n
n
a 1 = 10, and a 2 = 32. g) F(n) = 3?
14. Find the solution to a n = 5a n−2 − 4a n−4 with a 0 = 3, 27. What is the general form of the particular solution guaran-
a 1 = 2, a 2 = 6, and a 3 = 8. teed to exist by Theorem 6 of the linear nonhomogeneous
15. Find the solution to a n = 2a n−1 + 5a n−2 − 6a n−3 with recurrence relation a n = 8a n−2 − 16a n−4 + F(n) if
3
n
a 0 = 7, a 1 =−4, and a 2 = 8. a) F(n) = n ? b) F(n) = (−2) ?
n
2 n
∗ 16. Prove Theorem 3. c) F(n) = n2 ? d) F(n) = n 4 ?
2
n
4 n
e) F(n) = (n − 2)(−2) ? f) F(n) = n 2 ?
17. Prove this identity relating the Fibonacci numbers and the g) F(n) = 2?
binomial coefficients:
28. a) Find all solutions of the recurrence relation
2
f n+1 = C(n, 0) + C(n − 1, 1) + ··· + C(n − k, k), a n = 2a n−1 + 2n .
b) Find the solution of the recurrence relation in part (a)
where n is a positive integer and k = n/2
.[Hint: Let
with initial condition a 1 = 4.
a n = C(n, 0) + C(n − 1, 1) + ···+ C(n − k, k). Show
29. a) Find all solutions of the recurrence relation
that the sequence {a n } satisfies the same recurrence re-
n
a n = 2a n−1 + 3 .
lation and initial conditions satisfied by the sequence of
b) Find the solution of the recurrence relation in part (a)
Fibonacci numbers.]
with initial condition a 1 = 5.
18. Solve the recurrence relation a n = 6a n−1 − 12a n−2 +
30. a) Find all solutions of the recurrence relation a n =
8a n−3 with a 0 =−5,a 1 = 4, and a 2 = 88. n
−5a n−1 − 6a n−2 + 42 · 4 .
19. Solve the recurrence relation a n =−3a n−1 − 3a n−2 −
b) Find the solution of this recurrence relation with a 1 =
a n−3 with a 0 = 5,a 1 =−9, and a 2 = 15.
56 and a 2 = 278.
20. Find the general form of the solutions of the recurrence 31. Find all solutions of the recurrence relation a n =
relation a n = 8a n−2 − 16a n−4 . 5a n−1 − 6a n−2 + 2 + 3n.[Hint: Look for a particular
n
n
21. What is the general form of the solutions of a linear homo- solution of the form qn2 + p 1 n + p 2 , where q, p 1 , and
geneous recurrence relation if its characteristic equation p 2 are constants.]
has roots 1, 1, 1, 1, −2, −2, −2, 3, 3, −4? 32. Find the solution of the recurrence relation a n =
n
22. What is the general form of the solutions of a linear homo- 2a n−1 + 3 · 2 .
geneous recurrence relation if its characteristic equation 33. Find all solutions of the recurrence relation a n =
n
has the roots −1, −1, −1, 2, 2, 5, 5, 7? 4a n−1 − 4a n−2 + (n + 1)2 .