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

Today we will discover another Fibonacci identity: look for an identity of the form (Subscript[F, 3n])=a ((Subscript[F, n])^3)+b ((Subscript[F, n])^2)+c (Subscript[F, n]) for all n and some coefficients a,b,c

If we want to solve for coefficients a, b, c, we will need three equations.

First, try n = 1:

eq1=f[3*1]==a *f[1]^3+b*f[1]^2+c*f[1]

Next, try n = 2:

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

Next, try n = 3:

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

Next, try n = 4:

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

Solve eq1, eq3, and eq4 simultaneously:

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

Does this solution satisfy the identity for n=5?

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

eq5/.sol

125 a+25 b+5 c/.sol

Now try solving eq1, eq3, eq5:

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

Does this solution hold for n=7?

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

eq7/.sol

Does it hold for n=9?

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

eq9/.sol

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

checkConjecture[n_]:=Module[{lhs,rhs},
lhs=f[3n];
rhs=5f[n]^3-3f[n];
(*Print[{lhs,rhs}];*)
lhs==rhs
]

checkConjecture[7]

checkConjecture[9]

checkConjecture[8]

checkConjecture[11]

Check lots of odd n:

checkConjecture/@Range[1,99,2]

This is good evidence that the conjecture may be true!

Your Turn: Can you find a similar conjecture that holds for even n?

We observe that (Subscript[F, 3n])=5((Subscript[F, n])^3)+3(Subscript[F, n]) holds for even n.

Conjecture (the Fibonacci 3n Identity): The Fibonacci numbers satisfy (Subscript[F, 3n])=5((Subscript[F, n])^3)+(((-1))^n)3(Subscript[F, n]) for nonnegative integers n.

Can we generalize this? Try 4n, 5n, etc.

With n = 4: (Subscript[F, 4n])=((Subscript[aF, n])^4)+b ((Subscript[F, n])^3)+c ((Subscript[F, n])^2)+d (Subscript[F, n])

How about n=5? (Subscript[F, 5n])=25((Subscript[F, n])^5)+(((-1))^n)25((Subscript[F, n])^3)+5(Subscript[F, n]) is the “Fibonacci 5n Identity”.