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 n=0 separatey *)
If[n==0,Return[0]];

(* 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 b, which contains the nth Fibonacci number *)
b 
]

Try it out:

computeFib/@Range[0,10]

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

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

Ratios of consecutive Fibonacci numbers

Last time we briefly considered the ratios of consecutive Fibonacci numbers, ((Subscript[F, n])/(Subscript[F, n-1])) for various n. Here are some ways we can compute these ratios using our computeFib function:

N[computeFib[4]/computeFib[3]]

computeFib[6]/computeFib[5] //N

ratios=Table[computeFib[n]/computeFib[n-1],{n,2,50}]
ratios//N

It appears that these ratios have converged to some specific number. What number is this?

N[ratios[[-1]],20]

What about the ratios of Fibonacci numbers whose indexes differ by k > 1?

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 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.

Table[computeFib[n-1]*computeFib[n+1],{n,2,20}]

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

Table[computeFib[n]^2,{n,2,20}]

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.

Conjecture: The Fibonacci numbers satisfy (Subscript[F, n-1])(Subscript[F, n+1])-((Subscript[F, n])^2)=(((-1))^n) for all positive integers n.

Write a module to help verify your conjecture.

Suppose you conjecture that the identify 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.

Argument: 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=computeFib[n-1]*computeFib[n+1]-computeFib[n]^2;

(* compute the right hand side *)
rhs=(-1)^n;

(* 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.

verifyIdentity[10000]