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
1
//
nn+
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+12525,/5))
1 160/5/
32