Fibonacci Numbers

Math 242 Modern Computational Mathematics

Recall the definition of the Fibonacci numbers:

(Subscript[F, 0])=0, (Subscript[F, 1])=1
(Subscript[F, n])=(Subscript[F, n-1])+(Subscript[F, n-2])      for n>1

Computing the Fibonacci number (Subscript[F, n])

Here are three methods for computing the Fibonacci number (Subscript[F, n]) without storing a list of Fibonacci numbers.

1. Recursive Method

This is the first method we implemented in the previous class. It follows directly from the recursive definition of the Fibonacci numbers.

fib[0]=0
fib[1]=1
fib[n_]:=fib[n-1]+fib[n-2]

2. Iterative Method

Here is one version of the iterative method. It starts with two initial values a and b. Each time it computes a new value next=a+b, it stores b in a and next in b.

fibonacci[n_]:=Module[{a=0,b=1,next},
(* handle the base cases *)
If[n<=1,Return[n]];

(* here is the loop *)
Do[
(* compute the next value *)
next=a+b;

(* shift the values in memory *)
a=b;
b=next,

(* repeat n-1 times *)
n-1];

(* return the value b *)
b
]

Try it out:

3. Exact Formula Method

The Fibonacci numbers can also be computed from the exact formula given in Section 2.2 in the text:

(Subscript[F, n])=(1/(Sqrt[5]))[(((((1+(Sqrt[5]))/2)))^n)-(((((1-(Sqrt[5]))/2)))^n)]

Computing a list of Fibonacci numbers (Subscript[F, 0]),(Subscript[F, 1]),...,(Subscript[F, n])

Sometimes we want not just one Fibonacci number, but a list of Fibonacci numbers. There are several ways we could compute such a list.

1. Call one of the previous functions n times.

Since we already have functions that compute (Subscript[F, n]), we can call one of those functions n+1 times to compute (Subscript[F, 0]),(Subscript[F, 1]),...,(Subscript[F, n]).

2. Append values to a list

One approach is to start with a list of the two initial values. As new values are computed, append them to the list.

fibonacciList2[n_]:=Module[{fibList={0,1}},
(* use a loop to compute (Subscript[F, 2]) through (Subscript[F, n]) and append them to fibList *)



(* return the list *)
fibList
]

3. Start with an “empty” list

Another approach is to start with an “empty” list of the appropriate length. As new values are computed, store them in the list.

fibonacciList3[n_]:=Module[{fibList=Table[0,n+1]},
(* set the initial values (Subscript[F, 0]) and (Subscript[F, 1]) *)


(* compute (Subscript[F, 2]) through (Subscript[F, n]) and store them in the list *)


(* return the list *)
fibList
]