Fibonacci Identities

MATH 242 Modern Computational Mathematics

Fibonacci List Algorithm

Often it is helpful to have a module that returns not just a single Fibonacci number, but a list of the first n Fibonacci numbers. Here are two ways to write such a module.

Option 1: Append values to a list

We could start with the list {0,1} of initial values and append each successive Fibonacci number to the list. To append an item to a list is to add it onto the end of the list; this increases the size of the list in memory.

fibonacciList1[n_]:=Module[
(* initialize a list with (Subscript[F, 0]) and (Subscript[F, 1]) *)
{fibList={0,1}},

(* use a loop to compute (Subscript[F, 2]) through (Subscript[F, n]) and append them to fibList *)
Do[
AppendTo[fibList,fibList[[-1]]+fibList[[-2]]]
,
n-1];

(* return the list *)
fibList
]

fibonacciList1[10]

How efficient is this method? Let’s measure some runtimes.

nVals=Range[2000,30000,2000];
list1Runtime=Table[
ClearSystemCache[]; Timing[fibonacciList1[n]][[1]],
{n,nVals}]

Let’s make a plot of the runtimes:

ListPlot[list1Runtime,DataRange->{Min[nVals],Max[nVals]},AxesLabel->{"length of list","runtime"}]

It takes about a second to compute a list of size 30,000. The runtime plot looks something like a quadratic function.

Option 2: Start with an “empty” list and fill in the values

We could start with an “empty” list of the appropriate length. As new values are computed, we store them in the list. This way, we don’t have to change the size of the list in memory each time we compute another Fibonacci number.

fibonacciList2[n_]:=Module[
(* start with a list of zeros *)
{fibList=Table[0,n+1]},

(* the initial value (Subscript[F, 0]) is already set, but we must set (Subscript[F, 1]) *)
fibList[[2]]=1;

(* compute (Subscript[F, 2]) through (Subscript[F, n]) and store them in the list *)
Do[
fibList[[i]]=fibList[[i-1]]+fibList[[i-2]]
,
{i,3,n+1}];

(* return the list *)
fibList
]

How efficient is this? Let’s measure runtimes using the same values of n as before.

list2Runtime=Table[
ClearSystemCache[];Timing[fibonacciList2[n]][[1]],
{n,nVals}]
ListPlot[list2Runtime,DataRange->{Min[nVals],Max[nVals]},AxesLabel->{"length of list","runtime"}]

It appears to be much faster! Now we can compute the list of size 30,000 in about a tenth of a second! Let’s try larger values of n.

nVals=Range[10000,200000,10000];
list2Runtime=Table[
ClearSystemCache[];Timing[fibonacciList2[n]][[1]],
{n,nVals}]
ListPlot[list2Runtime,DataRange->{Min[nVals],Max[nVals]},AxesLabel->{"length of list","runtime"}]

This is quite fast! Also the runtime appears to increase linearly with the number of iterations.

Generalizing Cassini's Identity

Let’s investigate some more Fibonacci identities. For convenience, we will first compute a big list of Fibonacci numbers:

fibList=fibonacciList2[100000];

Unfortunately, the indexing of this list is off by one compared to the usual mathematical notation. In the usual notation (Subscript[F, 0])=0 and (Subscript[F, 1])=1, but in Mathematica fibList[[0]] is undefined and fibList[[1]] = 0, as shown here:

fibList[[0]]

fibList[[1]]

We can define a little function to adjust the indexes, matching the usual mathematical notation:

f[n_]:=fibList[[n+1]]

Note how this works:

f[0]

f[1]

f/@Range[0,10]

f[100]

Recall Cassini's Identity

Recall that Cassini’s identity says that (Subscript[F, n-1])(Subscript[F, n+1])-(Subscript[F, n]^2)=(((-1))^n). Can generalize this identity? Try replacing the 1s with a different number!

For example, compute  (Subscript[F, n-2])(Subscript[F, n+2])-(Subscript[F, n]^2) for various positive integers n. Can you conjecture an identity?

Table[f[n-2]f[n+2]-((f[n])^2),{n,2,30}]

Now consider  (Subscript[F, n-3])(Subscript[F, n+3])-(Subscript[F, n]^2). Can you conjecture an identity?

Table[f[n-3]f[n+3]-((f[n])^2),{n,3,30}]

How about  (Subscript[F, n-4])(Subscript[F, n+4])-(Subscript[F, n]^2) — can you conjecture an identity?

Table[f[n-4]f[n+4]-((f[n])^2),{n,4,30}]

Is there another identity for (Subscript[F, n-5])(Subscript[F, n+5])-(Subscript[F, n]^2)?

What pattern do you see? Conjecture an identity involving (Subscript[F, n-k])(Subscript[F, n+k])-(Subscript[F, n]^2) for integers n and k.

A 2D table might help organize your work. Here is an example of such a table:

TableForm[Table[n,{n,0,8},{k,0,5}],TableHeadings->{{"n=0","n=1","n=2","..."},{"k=0","k=1","k=2","..."}}]

Here is an example involving the Fibonacci numbers. Note the If statement to avoid negative indexes.

TableForm[Table[If[n-k>=0,f[n-k]f[n+k]-((f[n])^2)],{n,0,8},{k,0,5}],TableHeadings->{{"n=0","n=1","n=2","..."},{"k=0","k=1","k=2","..."}}]

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

Once you have a conjecture, write a module to test your conjecture for larger values of n and k.

More Fibonacci Identities

(Subscript[F, m+1])(Subscript[F, n+1])-(Subscript[F, m-1])(Subscript[F, n-1])

Consider the quantity (Subscript[F, m+1])(Subscript[F, n+1])-(Subscript[F, m-1])(Subscript[F, n-1]). Compute this quantity for various integers m and n. What patterns do you see? Conjecture an identity supported by your computational evidence.

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

Consider the quantity (Subscript[F, n])(Subscript[F, n+3]^2)-(Subscript[F, n+2]^3). Compute this quantity for various integers n. Conjecture an identity supported by your computational evidence.

Now generalize!

Can you generalize either of the expressions above? What new quantities would you like to compute? What patterns emerge?