Fibonacci Polynomial Identities

Math 242 Modern Computational Mathematics

Preliminary Code

Here is our Fibonacci list module from previous class sessions. This returns a list of Fibonacci numbers (Subscript[F, 0]),(Subscript[F, 1]),...,(Subscript[F, n]).

fibonacciList[n_]:=Module[{fibList=Table[0,n+1]},
(* set the initial values (Subscript[F, 0]) and (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
]

First we create a big list of Fibonacci numbers.

fibList=fibonacciList[1000];

Next we create a little function f to adjust the indexing to match the usual mathematical notation. (That is, (Subscript[F, 0])=0, (Subscript[F, 1])=1, etc.)

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

Finding Coefficients

Complete the following module to automate the process of find coefficients for the Fibonacci polynomial identities. The module accepts one parameter: an odd integer q. The module returns a list of coefficients for the Fibonacci q n identity. (This is Algorithm 2.15 in the text.)

findFibCoefficients[q_]:=Module[{nvals,matrix, vector,sol},
(* set up the nvals *)
nvals=Range[2,2q,2];
Print["nvals:",nvals];

(* set up the matrix *)
matrix=Table[f[n]^i,{n,nvals},{i,q,1,-1}];
Print["matrix:",MatrixForm[matrix]];

(* set up the vector *)
vector=Table[f[q*n],{n,nvals}];
Print["vector:",vector];

(* solve the system *)
sol=LinearSolve[matrix,vector];
Print["solution:",sol];

(* return the solution *)
sol
]

Testing :

findFibCoefficients[3]

findFibCoefficients[5]

findFibCoefficients[7]

findFibCoefficients[9]

Verifying the Fibonacci q n Identity

Now write a module that verifies the Fibonacci q n identity for lots of value of n. This module should accept as parameters an odd integer q, a list of coefficients, and a max value of n to check.  Output from the module should clearly indicate whether the identity holds or a counterexample is found.

Hint: First get your module working for even n, and then adapt it for both even and odd n.

verifyFibIdentity[q_,coeffs_,nMax_]:=Module[{},




]

Lucas Numbers

The Lucas numbers (Subscript[L, 0]), (Subscript[L, 1]),(Subscript[L, 2]),... are defined similarly to the Fibonacci numbers, except that the first number is 2, not 0. Specifically:

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

Complete the following code to compute the Lucas numbers. It should be very similar to the Fibonacci code at the top of this notebook.

lucasList[n_]:=Module[{lucList=Table[0,n+1]},
(* set the initial values (Subscript[L, 0]) and (Subscript[L, 1]) *)
lucList[[1]]=2;
lucList[[2]]=1;

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

(* return the list *)
lucList
]

Make sure it works. It should return the list 2,1,3,4,7,11,18,29,...

lucasList[10]

Next we create a big list of Lucas numbers.

lucList=lucasList[1000];

Now we create a little function l to adjust the indexing to match the usual mathematical notation.

l[n_]:=lucList[[n+1]]