198
Recursion, Recurrence Relations, and Analysis of Algorithms
3. F(1) = 2
F(n) = 2F(n − 1) + 2
n
for n ≥ 2
4. T(1) = 1
T(n) = 2T(n − 1) + 1 for n ≥ 2
(Hint: See Example 15 in Section 2.2.)
5. A(1) = 1
A(n) = A(n − 1) + n for n ≥ 2
(Hint: See Practice 7 in Section 2.2.)
6. S(1) = 1
S(n) = S(n − 1) + (2n − 1) for n ≥ 2
(Hint: See Example 14 in Section 2.2.)
7. T(1) = 1
T(n) = T(n − 1) + n
2
for n ≥ 2
(Hint: See Exercise 7 in Section 2.2.)
8. P(1) = 2
P(n) = 2P(n − 1) + n2
n
for n ≥ 2
(Hint: See Practice 7 in Section 2.2.)
9. F(1) = 1
F(n) = nF(n − 1) for n ≥ 2
10. S(1) = 1
S(n) = nS(n − 1) + n! for n ≥ 2
11. A(1) = 1
A(n) = 2(n − 1)A(n − 1) for n ≥ 2
(Hint: 0! is defined to equal 1.)
12. P(1) = 2
P(n) = 3(n + 1)P(n − 1) for n ≥ 2
13. At the beginning of this chapter the contractor claimed:
The material to be stored at the chemical disposal site degrades to inert matter at the rate of 5% per
year. Therefore only about one-third of the original active material will remain at the end of 20 years.
a. Write a recurrence relation T(n) for the amount of active material at the beginning of year n. Assume
that T(1) = X, a specific but unknown amount.
b. Solve the recurrence relation.
c. Compute T(21) to check the contractor’s claim; note that the end of 20 years is the beginning of the
21st year.
14. A colony of bats is counted every 2 months. The first four counts are 1200, 1800, 2700, and 4050.
a. Assuming that this growth rate continues, write a recurrence relation for the number of bats at count n.
b. Solve the recurrence relation.
c. What will the 12th count be?
15. Spam e-mail containing a virus is sent to 1,000 e-mail addresses. After 1 second, a recipient machine
broadcasts 10 new spam e-mails containing the virus, after which the virus disables itself on that
machine.