Page 547 - Discrete Mathematics and Its Applications

526 8 / Advanced Counting Techniques

34. Find all solutions of the recurrence relation a n = where a 0 = 0 and a 1 = 1 in terms of the Fibonacci num-
7a n−1 − 16a n−2 + 12a n−3 + n4 n with a 0 =−2, bers. [Hint: Let b n = a n + 1 and apply Exercise 42 to the
a 1 = 0, and a 2 = 5. sequence b n .]
∗
35. Find the solution of the recurrence relation a n = 44. (Linear algebra required) Let A n be the n × n matrix
n
4a n−1 − 3a n−2 + 2 + n + 3 with a 0 = 1 and a 1 = 4. with 2s on its main diagonal, 1s in all positions next to a
diagonal element, and 0s everywhere else. Find a recur-
36. Let a n be the sum of the first n perfect squares, that
n 2 rence relation for d n , the determinant of A n . Solve this
is, a n = k . Show that the sequence {a n } sat-
k = 1 recurrence relation to find a formula for d n .
isfies the linear nonhomogeneous recurrence relation
2
a n = a n−1 + n and the initial condition a 1 = 1. Use 45. Suppose that each pair of a genetically engineered species
Theorem 6 to determine a formula for a n by solving this of rabbits left on an island produces two new pairs of rab-
recurrence relation. bits at the age of 1 month and six new pairs of rabbits at
the age of 2 months and every month afterward. None of
37. Let a n be the sum of the first n triangular numbers, that is, the rabbits ever die or leave the island.
n
t
a n = k = 1 k , where t k = k(k + 1)/2. Show that {a n } a) Find a recurrence relation for the number of pairs of
satisfies the linear nonhomogeneous recurrence relation rabbits on the island n months after one newborn pair
a n = a n−1 + n(n + 1)/2andtheinitialconditiona 1 = 1. is left on the island.
Use Theorem 6 to determine a formula for a n by solving
this recurrence relation. b) By solving the recurrence relation in (a) determine
the number of pairs of rabbits on the island n months
38. a) Find the characteristic roots of the linear homo- after one pair is left on the island.
geneous recurrence relation a n = 2a n−1 − 2a n−2 .
46. Suppose that there are two goats on an island initially.
[Note: These are complex numbers.]
The number of goats on the island doubles every year by
b) Find the solution of the recurrence relation in part (a) natural reproduction, and some goats are either added or
with a 0 = 1 and a 1 = 2. removed each year.
∗ 39. a) Find the characteristic roots of the linear homoge- a) Construct a recurrence relation for the number of
neous recurrence relation a n = a n−4 .[Note: These goats on the island at the start of the nth year, as-
include complex numbers.] suming that during each year an extra 100 goats are
put on the island.
b) Find the solution of the recurrence relation in part (a)
with a 0 = 1, a 1 = 0, a 2 =−1, and a 3 = 1. b) Solve the recurrence relation from part (a) to find the
number of goats on the island at the start of the nth
∗ 40. Solve the simultaneous recurrence relations
year.
a n = 3a n−1 + 2b n−1 c) Construct a recurrence relation for the number of
goats on the island at the start of the nth year, as-
b n = a n−1 + 2b n−1
suming that n goats are removed during the nth year
with a 0 = 1 and b 0 = 2. for each n ≥ 3.
∗ 41. a) Use the formula found in Example 4 for f n , the nth d) Solve the recurrence relation in part (c) for the number
Fibonacci number, to show that f n is the integer of goats on the island at the start of the nth year.
closest to 47. A new employee at an exciting new software company
n starts with a salary of $50,000 and is promised that at the
√
1 1 + 5 end of each year her salary will be double her salary of
√ .
5 2 the previous year, with an extra increment of $10,000 for
each year she has been with the company.
b) Determine for which nf n is greater than a) Construct a recurrence relation for her salary for her
√
n nth year of employment.
1 1 + 5
√ b) Solve this recurrence relation to find her salary for her
5 2 nth year of employment.
Some linear recurrence relations that do not have constant co-
and for which nf n is less than
efficients can be systematically solved. This is the case for
√ recurrence relations of the form f (n)a n = g(n)a n−1 + h(n).
n
1 1 + 5
√ . Exercises 48–50 illustrate this.
5 2 ∗ 48. a) Show that the recurrence relation
f (n)a n = g(n)a n−1 + h(n),
42. Show that if a n = a n−1 + a n−2 , a 0 = s and a 1 = t,
where s and t are constants, then a n = sf n−1 + tf n for
for n ≥ 1, and with a 0 = C, can be reduced to a re-
all positive integers n.
currence relation of the form
43. Express the solution of the linear nonhomogenous
recurrence relation a n = a n−1 + a n−2 + 1 for n ≥ 2 b n = b n−1 + Q(n)h(n),