202
Recursion, Recurrence Relations, and Analysis of Algorithms
39. Houses in a new development go on sale initially for an average price of $200,000. At the beginning of
month 2, the average sale price has risen to $250,000. At the beginning of each succeeding month, the
average price increase is half what it was the previous month.
a. Write and solve a recurrence relation for M(n), the average sale price at the beginning of month n.
b. At the beginning of which month is the average price within $2,000 of $300,000?
40. A contaminated soil site is tested monthly for the presence of a particular microorganism. Initially,
950 microorganisms per cubic foot of soil are found; at the beginning of month 2, there are 1,000 organisms per cubic foot. Left untreated, the growth rate of this microorganism increases by 25% per month.
a. Write and solve a recurrence relation for O(n), the number of organisms present per cubic foot at the
beginning of month n.
b. At the end of what month does the number of organisms first exceed 5,000 per cubic foot?
41. Prove that the number of binary strings of length n with no two consecutive 0s is given by the Fibonacci
sequence term F(n + 2). (Hint: Write a recurrence relation; consider strings of length n that end in 1 and
those that end in 0.)
42. a. Find a recurrence relation for the number of binary strings of length n that have two consecutive 1s.
b. How many binary strings of length 4 have two consecutive 1s? What are these strings?
43. Consider the recurrence relation S(n) = c 1 S(n − 1) as a linear second-order homogeneous recurrence
relation with constant coefficients where c 2 = 0. Solve this recurrence relation using its characteristic
equation, and prove that the solution is the same as that of Equation (8).
44. Prove that
S(n) = pr
n−1
+ q(n − 1)r
n−1
where
p = S(1)
pr + qr = S(2)
is a solution to the recurrence relation S(n) = c 1 S(n − 1) + c 2 S(n − 2) for all n ≥ 1 if r is a repeated root
of the characteristic equation.
In Exercises 45–48, solve the recurrence relation subject to the basis step. (Hint: See Example 15 in Section 2.2,
and note that 2
log n
= n.)
45. P(1) = 1
P(n) = 2Pa
n
2
b + 3 for n ≥ 2, n = 2
m
46. T(1) = 3
T(n) = Ta
n
2
b + n for n ≥ 2, n = 2
m
47. S(1) = 1
S(n) = 2Sa
n
2
b + n for n ≥ 2, n = 2
m
48. P(1) = 1
P(n) = 2Pa
n
2
b + n
2
for n ≥ 2, n = 2
m
Recursion, Recurrence Relations, and Analysis of Algorithms
39. Houses in a new development go on sale initially for an average price of $200,000. At the beginning of
month 2, the average sale price has risen to $250,000. At the beginning of each succeeding month, the
average price increase is half what it was the previous month.
a. Write and solve a recurrence relation for M(n), the average sale price at the beginning of month n.
b. At the beginning of which month is the average price within $2,000 of $300,000?
40. A contaminated soil site is tested monthly for the presence of a particular microorganism. Initially,
950 microorganisms per cubic foot of soil are found; at the beginning of month 2, there are 1,000 organisms per cubic foot. Left untreated, the growth rate of this microorganism increases by 25% per month.
a. Write and solve a recurrence relation for O(n), the number of organisms present per cubic foot at the
beginning of month n.
b. At the end of what month does the number of organisms first exceed 5,000 per cubic foot?
41. Prove that the number of binary strings of length n with no two consecutive 0s is given by the Fibonacci
sequence term F(n + 2). (Hint: Write a recurrence relation; consider strings of length n that end in 1 and
those that end in 0.)
42. a. Find a recurrence relation for the number of binary strings of length n that have two consecutive 1s.
b. How many binary strings of length 4 have two consecutive 1s? What are these strings?
43. Consider the recurrence relation S(n) = c 1 S(n − 1) as a linear second-order homogeneous recurrence
relation with constant coefficients where c 2 = 0. Solve this recurrence relation using its characteristic
equation, and prove that the solution is the same as that of Equation (8).
44. Prove that
S(n) = pr
n−1
+ q(n − 1)r
n−1
where
p = S(1)
pr + qr = S(2)
is a solution to the recurrence relation S(n) = c 1 S(n − 1) + c 2 S(n − 2) for all n ≥ 1 if r is a repeated root
of the characteristic equation.
In Exercises 45–48, solve the recurrence relation subject to the basis step. (Hint: See Example 15 in Section 2.2,
and note that 2
log n
= n.)
45. P(1) = 1
P(n) = 2Pa
n
2
b + 3 for n ≥ 2, n = 2
m
46. T(1) = 3
T(n) = Ta
n
2
b + n for n ≥ 2, n = 2
m
47. S(1) = 1
S(n) = 2Sa
n
2
b + n for n ≥ 2, n = 2
m
48. P(1) = 1
P(n) = 2Pa
n
2
b + n
2
for n ≥ 2, n = 2
m