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

Iterative Fibonacci

In the last class, we wrote an iterative function that computes Fibonacci numbers. Here is a version of that function. It accepts one parameter, n, and returns (Subscript[F, n]), the nth Fibonacci number. (This is similar to Pseudocode 2.3 in the text.)

computeFib[n_]:=Module[
(* initial values *)
{a=0,b=1,next},

(* handle initial cases separately *)
If[n<=1,Return[n]];

(* main loop *)  
Do[
next=a+b;    (* compute the next Fibonacci number *)
a=b;                 (* shift b to a *)
b=next,           (* shift next to b *)
{k,2,n}];

(* return next, which contains the nth Fibonacci number *)
next 
]

Try it out:

computeFib/@Range[0,10]

It appears to work. Try computing some more Fibonacci numbers:

computeFib/@{50,100,150,200}

Ratios of Fibonacci numbers

Consecutive Fibonacci numbers

Compute the ratios of consecutive Fibonacci numbers, ((Subscript[F, n])/(Subscript[F, n-1])) for various n. What do you notice?

What if the indexes differ by 2? ...or 3? ...or more?

Compute ratios ((Subscript[F, n])/(Subscript[F, n-2])) for various n. What do you notice?

Compute ratios ((Subscript[F, n])/(Subscript[F, n-3])) for various n. What do you notice?

Compute ratios ((Subscript[F, n])/(Subscript[F, n-4])) for various n. What do you notice?

What is the general pattern?

What do you think is the value of (lim_(n->∞))((Subscript[F, n])/(Subscript[F, n-k])) for k=1,2,3,...? If you have a guess, can you prove that your guess is correct?

A Fibonacci Identity

Compute (Subscript[F, n-1])(Subscript[F, n+1]) for various positive integers n.

Compute (Subscript[F, n]^2) for various positive integers n.

What do you notice about your previous two results? State a conjecture. Then test your conjecture with some larger values of n than you used previously.

Write a module to help verify your conjecture.

Suppose you conjecture that the identity f(n)=g(n) holds for all positive integers n. A good way to test your conjecture is to write a module as follows. The module accepts a parameter nMax. The module uses a loop to test whether f(n)=g(n) for positive integers n=1,2,3,.... If the module finds an integer n such that f(n)!=g(n), then it returns that value n. However, if the identity holds for all n up to nMax, then the module returns nMax+1. Fill in the missing code to complete this module below.

Parameter: a positive integer nMax
Return: a positive integer n∈{1,2,...,nMax+1}
		If n<=nMax, then the identity fails at index n.
		If n=nMax+1, then the identity is true up to nMax.

verifyIdentity[nMax_]:=Module[{lhs,rhs},
Do[
(* compute the left hand side *)
lhs=

(* compute the right hand side *)
rhs=

(* print values *)
Print[{n,lhs,rhs,lhs==rhs}];

(* if lhs!=rhs, then return index n at which this occurs *)
If[lhs!=rhs,Return[n,Module]];

(* repeat for n from 1 to nMax*)
,{n,1,nMax}];

(* If we get here, then the identity holds up to nMax. Indicate this by returning nMax+1 *)
nMax+1
]

Now test your module.