200
Recursion, Recurrence Relations, and Analysis of Algorithms
b. Solve this recurrence relation. (Hint: See Exercise 15 in Section 2.2.)
c. Go through the steps of the solution algorithm for n = 3 and record the number of disk moves required.
Compare this number with the result from part (b) with n = 3.
d. The mythical origin of the Towers of Hanoi puzzle concerns 64 golden disks that a group of monks are
moving from one tower to another. When their task is complete, the world will end. Assuming that the
monks can move 1 disk per second, calculate the number of years to complete the task.
23. Early members of the Pythagorean Society defined figurate numbers to be the number of dots in certain
geometrical configurations. The first few triangular numbers are 1, 3, 6, and 10:
1
3
6
1 0
Find and solve a recurrence relation for the nth triangular number. (Hint: See Practice 7 in Section 2.2.)
24. The first few square numbers (see the previous Exercise) are 1, 4, 9, and 16:
16
1
9
4
Find and solve a recurrence relation for the nth square number. (Hint: See Example 14 in Section 2.2.)
25. The first few pentagonal numbers (see Exercise 23) are 1, 5, 12, and 22:
1
5
12
22
Find and solve a recurrence relation for the nth pentagonal number. (Hint: See Exercise 28 of Section 2.2
for the formula for the sum of an arithmetic sequence.)
26. Use induction to verify that equation (8) of this section is the solution to the recurrence relation (6) subject
to the basis condition that S(1) is known.
In Exercises 27–34, solve the recurrence relation subject to the initial conditions.
27. T(1) = 5
T(2) = 11
T(n) = 5T(n − 1) − 6T(n − 2) for n ≥ 3