Fibonacci Polynomial Identities

Math 242 Modern Computational Mathematics

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[{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=f[3]==a*f[1]^3+b*f[1]^2+c*f[1]

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

eq2=f[6]==a*f[2]^3+b*f[2]^2+c*f[2]

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=f[9]==a*f[3]^3+b*f[3]^2+c*f[3]

Next, let’s try n=4:

eq4=f[12]==a*f[4]^3+b*f[4]^2+c*f[4]

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

sol=Solve[{eq1,eq3,eq4},{a,b,c}]

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

eq5=f[15]==a*f[5]^3+b*f[5]^2+c*f[5]

eq5/.sol

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

sol=Solve[{eq2,eq3,eq4},{a,b,c}]

eq5/.sol

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

sol=Solve[{eq1,eq3,eq5},{a,b,c}]

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

eq7=f[21]==a*f[7]^3+b*f[7]^2+c*f[7]

eq7/.sol

Wow! Does this solution work for n=9?

eq9=f[27]==a*f[9]^3+b*f[9]^2+c*f[9]

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},
lhs=f[3n];
rhs=5f[n]^3-3f[n];
lhs==rhs
]

results=checkOddN/@Range[1,99,2]

Tally[results]

Conjecture: The Fibonacci numbers satisfy (Subscript[F, 3n])=5(Subscript[F, n]^3)-3(Subscript[F, n]) for odd positive integers n.

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?

Let's consider (Subscript[F, 3n])=a ((Subscript[F, n])^3)+b ((Subscript[F, n])^2)+c (Subscript[F, n]) for n=2,4,6. We’ll set up a vector for the left side and a matrix for the right side:

vec2={f[3*2],f[3*4],f[3*6]}

mat2={{f[2]^3,f[2]^2,f[2]},{f[4]^3,f[4]^2,f[4]},{f[6]^3,f[6]^2,f[6]}}
MatrixForm[matrix]

Now solve the linear system:

Inverse[mat2].vec2

Interesting -- the only difference is that the -3 is now +3. Let’s check more even values of n:

checkEvenN[n_]:=Module[{lhs,rhs},
lhs=f[3n];
rhs=5f[n]^3+3f[n];
lhs==rhs
]

res2=checkEvenN/@Range[2,100,2]

Tally[res2]

We observe that (Subscript[F, 3n])=5(Subscript[F, n]^3)-3(Subscript[F, n]) if n is odd, and (Subscript[F, 3n])=5(Subscript[F, n]^3)+3(Subscript[F, n]) if n is even. We can combine both of these statements in the following conjecture:

Conjecture: The Fibonacci numbers satisfy (Subscript[F, 3n])=5(Subscript[F, n]^3)+(((-1))^n)3(Subscript[F, n]) for all nonnegative integers 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])?

Let's consider (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]) for n=2,4,6,8,10. We’ll set up a vector for the left side and a matrix for the right side.

vec5={f[5*2],f[5*4],f[5*6],f[5*8],f[5*10]}

Note that we could do this more easily with Table:

vec5=Table[f[5n],{n,2,10,2}]

Now the matrix:

mat5={{((f[2])^5),((f[2])^4),((f[2])^3),((f[2])^2),f[2]},{((f[4])^5),((f[4])^4),((f[4])^3),((f[4])^2),f[4]},{((f[6])^5),((f[6])^4),((f[6])^3),((f[6])^2),f[6]},{((f[8])^5),((f[8])^4),((f[8])^3),((f[8])^2),f[8]},{((f[10])^5),((f[10])^4),((f[10])^3),((f[10])^2),f[10]}}

Could you write the above line more simply with Table?

Now solve for the coefficients:

sol5=Inverse[mat5].vec5

It looks like (Subscript[F, 5n])=25(Subscript[F, n]^5)+25(Subscript[F, n]^3)+5(Subscript[F, n]) for positive even integers n. Check this for more even n:

checkEven5N[n_]:=Module[{lhs,rhs},
lhs=f[5n];
rhs=25f[n]^5+25f[n]^3+5f[n];
lhs==rhs
]

res5=checkEven5N/@Range[2,100,2]

Tally[res5]

Similarly consider the 5n identity for odd values of n. You should arrive at the following conjecture:

Conjecture: The Fibonacci numbers satisfy (Subscript[F, 5n])=25(Subscript[F, n]^5)+(((-1))^n)25(Subscript[F, n]^3)+5(Subscript[F, n]) for all nonnegative integers 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.

Explore! What do you discover?