Discrete Mathematics for Computer Science

Fibonacci Recurrence Relation 561

(a) Use the algorithm described to find the matrix product for

( ) (;2)

(b) For matrices of size 2 r x 2 r, partition them into 2 r-1 x 2 r-1 submatrices, and

use the procedure shown for 2 x 2 matrices to compute the product. Carry out this

process for the following matrices:

(^352 2\^27

3

487 5I 9 946

4 69 9I 3 5 981

(3697/ (5s321)

(c) Show that matrix multiplication using this algorithm satisfies the recurrence

relation

fr = 7fr-1 + 18.2r-^2 for r > 1

Solve this recurrence. How does this result compare with the classical method of

multiplying matrices?

25. Write a procedure to solve the general n-disk Tower of Hanoi problem using the fol-
    lowing idea: Number the disks from smallest to largest, starting at 1. Consider the
    towers as being in a triangular formation with the pegs numbered counterclockwise.
    Describe the disk moved and the direction it should be moved where XC means move
    the top disk on peg X in a clockwise direction to the next peg and XA means to move
    the top disk on peg X in a counterclockwise direction. For example, the following

moves solve the problem for n = 3:

IC 2A 1C 3C IC 2A IC

Draw pictures of the three towers and how the disks are positioned for each of the

moves indicated.

Fibonacci Recurrence Relation

The Fibonacci sequence is the sequence of numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

This sequence is defined by a recurrence relation that gives the nth Fibonacci number as a

function of the (n - 1)-st and (n - 2)-nd Fibonacci numbers. The recurrence relation that

defines the terms of this sequence is

Fn Fn-1 + Fn-2 for n > 2

F =I

F 0 = I

The recurrence relation has order two, since F, is given in terms of the two preceding

values of the recurrence relation. (For a fuller description of the background of the recur-
rence relation, see Section 1.8.3). To calculate Fn, begin by calculating all the preceding