176
Recursion, Recurrence Relations, and Analysis of Algorithms
41. A sequence is recursively defined by
S(0) = 1
S(1) = 1
S(n) = 2S(n − 1) + S(n − 2) for n ≥ 2
a. Prove that S(n) is an odd number for n ≥ 0.
b. Prove that S(n) < 6S(n − 2) for n ≥ 4.
42. A sequence is recursively defined by
T(0) = 1
T(1) = 2
T(n) = 2T(n − 1) + T(n − 2) for n ≥ 2
Prove that T(n) ≤ A
5
2 B
n
for n ≥ 0.
43. Write a recursive definition for a geometric progression with initial term a and common ratio r (see
Exercise 27, Section 2.2.).
44. Write a recursive definition for an arithmetic progression with initial term a and common difference d (see
Exercise 28, Section 2.2.).
45. In an experiment, a certain colony of bacteria initially has a population of 50,000. A reading is taken every
2 hours, and at the end of every 2-hour interval, there are 3 times as many bacteria as before.
a. Write a recursive definition for A(n), the number of bacteria present at the beginning of the nth time
period.
b. At the beginning of which interval are there 1,350,000 bacteria present?
46. An amount of $500 is invested in an account paying 1.2% interest compounded annually.
a. Write a recursive definition for P(n), the amount in the account at the beginning of the nth year.
b. After how many years will the account balance exceed $570?
47. A set T of numbers is defined recursively by
1. 2 belongs to T.
2. If x belongs to T, so does x + 3 and 2 * x.
Which of the following numbers belong to T?
a. 6
b. 7
c. 19
d. 12
48. A set M of numbers is defined recursively by
1. 2 and 3 belong to M.
2. If x and y belong to M, so does x * y.
Which of the following numbers belong to M?
a. 6
b. 9
c. 16
d. 21
e. 26
f. 54
g. 72
h. 218