Discrete Mathematics for Computer Science

Fibonacci Recurrence Relation 565

1F,/5=A -I-B-)

Fo =1 =A + B

( 2

F, I A (± 2 v) +B (1 2 5)

1I=A+tB 1 A+ B

2 2
The solution of this system of equations is

A=7 --

and

Therefore, the solution of the Fibonacci recurrence relation
F= F-l + Fn-2

with initial conditions F 0 = 1 and F 1 = 1 is

1 / ,- \

1 nn+^1 // l

Fn = -75I - 5 2

It is instructive to evaluate this function for some small values of n to see that this
is, indeed, the solution as well as to provide an additional check that all the arithmetic is
correct:

1 +1

1 1 12 2

2'5= + 2 2i75 +^2

=1

1 (11'5

F 4 =

1 (1I + /5-+50+50O50 + 125 +25V,4

= • 32

I (1-5-5+50o-o50±15+125- 25,/5))

1 160/5-

/ 32