Fibonacci Identities

Math 242 Modern Computational Math, spring 2021

We will start with an improved module to compute (Subscript[F, n]), the nth Fibonacci number. Note that this module contains If statements to handle two special cases.

computeFib[n_Integer]:=Module[{a=0,b=1,next},
If[n<0,Return["invalid"]];
If[n==0,Return[0]];
Do[
next=a+b;  (* compute the next value *)
a=b;               (* shift b to a *)
b=next,        (* shift next to b *)
n-1
];
b       (* return b, which contains the nth Fibonacci number *)
]

Make sure it works:

computeFib/@Range[0,10]

Note what happens if n=-1:

computeFib[-1]

Cassini’s Identity

A basic Fibonacci Identity is Cassini's identity:

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

Let's explore and confirm that this identity holds.

Verifying Cassini’s identity using lists

First, make a list of m (say, twenty) Fibonacci values:

m=20;
fibs=computeFib/@Range[m]

Squaring these values is easy, this gives us ((Subscript[F, n])^2).

fibsSquared=fibs*fibs

Next, we get the shifted product (Subscript[F, n+1])(Subscript[F, n-1]). To do so, we need to slice the list of Fibonacci numbers.

fibsA=fibs[[3;;m]]
fibsB=fibs[[1;;(m-2)]]

We get (Subscript[F, n+1])(Subscript[F, n-1]) by multiplying.

fibsProduct=fibsA*fibsB

Now all we need to do is line up fibsSquared and fibsProduct and check that everything is correct. However, consider their lengths:

Length[fibsProduct]
Length[fibsSquared]

We need to trim the first and last elements of fibsSquared list. Then we can finally compute ((Subscript[F, n])^2)-(Subscript[F, n+1])(Subscript[F, n-1]) for a bunch of indexes all at once:

finalFibs=fibsSquared[[2;;(m-1)]]-fibsProduct

finalFibs==Table[(-1)^n,{n,1,m-2}]

As desired! If desired, the value of m can be made to be much larger. If m is very large, it would be best to use a semi-colon at the end of each computation to avoid printing huge lists.

Verifying Cassini’s identity using a module

Another approach is to write a module that verifies (Subscript[F, n]^2)-(Subscript[F, n+1])(Subscript[F, n-1])=(((-1))^(n-1)) for a particular choice of n.

verifyCassini[n_]:=Module[{},


(* complete the module here *)


]

Try it out:

result=verifyCassini /@Range[10]

We can also use the Select function to search the result list for any entry that is not True:

Select[result, (#≠True)&]

Note: The final ampersand in the Select statement above tells Mathematica that the second argument is a pure function. See the  Mathematica documentation for details.

Investigation 1

Consider the following quantity:

(Subscript[F, n]^2) - (Subscript[F, n+r])(Subscript[F, n-r])

Note that if r=1, then this gives Cassini’s Identity. Choose a different value for r and then evaluate the quantity for lots of values of n. Do you notice a pattern? Experiment with at least three values of r; for each, try at least 100 values of n.

Investigation 2

Now consider the following quantity:

(Subscript[F, n+i])(Subscript[F, n+j]) - (Subscript[F, n])(Subscript[F, n+i+j])

Choose some values for n, i, j and then evaluate the quantity. Do you notice a pattern? Experiment with at least six pairs of i,j; for each, try at least 100 values of n.