Fibonacci Polynomial Identities

MATH 242 Modern Computational Mathematics

Return Values in Mathematica

The following two modules are nearly the same. Can you spot how they are different? Observe this affects their behavior when you run them!

test1[]:=Module[
{},
Do[
Print[i];
If[i==5,Return["hi"]],
{i,1,10}
];
"finished"
]

test2[]:=Module[
{},
Do[
Print[i];
If[i==5,Return["hi",Module]],
{i,1,10}
];
"finished"
]

Fibonacci List Module (from last class)

Here is our module from last time that takes a positive integer n and returns a list of the Fibonacci numbers (Subscript[F, 0]), (Subscript[F, 1]), (Subscript[F, 2]), ..., (Subscript[F, n]).

fibonacciList[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
]

First we will create a big list of Fibonacci numbers:

fibList=fibonacciList[100000];

Next we will define a function f[n] to fix up the indexing:

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

Confirm that it works:

f/@Range[0,10]

A Fibonacci Polynomial Identity

Might the Fibonacci numbers satisfy (Subscript[F, 3n])=a ((Subscript[F, n])^3)+b ((Subscript[F, n])^2)+c (Subscript[F, n]) for some coefficients a, b, and c?

Since there are three unknown coefficients, we will need to set up and simultaneously solve three equations.

First, let’s try n=1 to produce an equation:

eq1=

Let’s try n=2 to get our second equation:

eq2=

Unfortunately we can’t solve these first two equations simultaneously, but let’s create a few more equations and see what we find. Try n=3 next:

eq3=

Next, let’s try n=4:

eq4=

Now let's see if we can solve equations eq1, eq3, and eq4 simultaneously:

sol=

We found a solution, and it consists of integer values. Does this solution satisfy the equation for n=5?

eq5=

eq5/.sol

What if we had used equations eq2, eq3, and eq4? Might we find a solution that satisfies eq5?

sol=

eq5/.sol

OK, let’s try something else. What if we try solving eq1, eq3, and eq5?

sol=

We find another solution with integer coefficients. Does this solution work for the equation with n=7?

eq7=

eq7/.sol

Wow! Does this solution work for n=9?

eq9=

eq9/.sol

Amazing! So we have found that (Subscript[F, 3n])=5((Subscript[F, n])^3)-3(Subscript[F, n]) when n is 1, 3, 5, 7, and 9. Does (Subscript[F, 3n])=5((Subscript[F, n])^3)-3(Subscript[F, n]) holds for other odd n also? Let’s find out!

checkOddN[n_]:=Module[{lhs,rhs},



]

results=

Tally[results]

Solving linear systems

In the code above, we defined and solved a system of linear equations. It’s often more convenient to do this using vectors and matrices. Recall the equations eq1, eq3, and eq5:

eq1
eq3
eq5

Let’s solve this system of equations using matrices. First, we’ll define a vector for the constants on the left side of the equations:

vector={f[3],f[9],f[15]}

Now we'll define a matrix for the coefficients on the right side of the equations:

matrix={{f[1]^3,f[1]^2,f[1]},{f[3]^3,f[3]^2,f[3]},{f[5]^3,f[5]^2,f[5]}}
MatrixForm[matrix]

Our matrix equation is of the form V=M X. To solve, we compute (M^(-1)) V=X. We could do this in either of the following two ways:

Inverse[matrix].vector

LinearSolve[matrix, vector]

With either method, we obtain the same solution as before.

Questions to Investigate

1. Is there a similar identity that holds for even n?

2. Is there a Fibonacci 5n identity of the form (Subscript[F, 5n])=(Subscript[a, 5])(Subscript[F, n]^5)+(Subscript[a, 4])(Subscript[F, n]^4)+(Subscript[a, 3])(Subscript[F, n]^3)+(Subscript[a, 2])(Subscript[F, n]^2)+(Subscript[a, 1])(Subscript[F, n])?

3. Are there similar identities for other multiples of n? Explore! Consider formulas whose left side is (Subscript[F, 2n]), (Subscript[F, 4n]), (Subscript[F, 6n]), (Subscript[F, 7n]), etc.