Puneet Varma (Editor)

Fibonacci polynomials

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Fibonacci polynomials

In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.

Contents

Definition

These Fibonacci polynomials are defined by a recurrence relation:

F n ( x ) = { 0 , if  n = 0 1 , if  n = 1 x F n − 1 ( x ) + F n − 2 ( x ) , if  n ≥ 2

The first few Fibonacci polynomials are:

F 0 ( x ) = 0 F 1 ( x ) = 1 F 2 ( x ) = x F 3 ( x ) = x 2 + 1 F 4 ( x ) = x 3 + 2 x F 5 ( x ) = x 4 + 3 x 2 + 1 F 6 ( x ) = x 5 + 4 x 3 + 3 x

The Lucas polynomials use the same recurrence with different starting values: L n ( x ) = { 2 , if  n = 0 x , if  n = 1 x L n − 1 ( x ) + L n − 2 ( x ) , if  n ≥ 2.

The first few Lucas polynomials are:

L 0 ( x ) = 2 L 1 ( x ) = x L 2 ( x ) = x 2 + 2 L 3 ( x ) = x 3 + 3 x L 4 ( x ) = x 4 + 4 x 2 + 2 L 5 ( x ) = x 5 + 5 x 3 + 5 x L 6 ( x ) = x 6 + 6 x 4 + 9 x 2 + 2.

The Fibonacci and Lucas numbers are recovered by evaluating the polynomials at x = 1; Pell numbers are recovered by evaluating Fn at x = 2. The degrees of Fn is n − 1 and the degree of Ln is n. The ordinary generating function for the sequences are:

∑ n = 0 ∞ F n ( x ) t n = t 1 − x t − t 2 ∑ n = 0 ∞ L n ( x ) t n = 2 − x t 1 − x t − t 2 .

The polynomials can be expressed in terms of Lucas sequences as

F n ( x ) = U n ( x , − 1 ) , L n ( x ) = V n ( x , − 1 ) .

Identities

As particular cases of Lucas sequences, Fibonacci polynomials satisfy a number of identities.

First, they can be defined for negative indices by

F − n ( x ) = ( − 1 ) n − 1 F n ( x ) , L − n ( x ) = ( − 1 ) n L n ( x ) .

Other identities include:

F m + n ( x ) = F m + 1 ( x ) F n ( x ) + F m ( x ) F n − 1 ( x ) L m + n ( x ) = L m ( x ) L n ( x ) − ( − 1 ) n L m − n ( x ) F n + 1 ( x ) F n − 1 ( x ) − F n ( x ) 2 = ( − 1 ) n F 2 n ( x ) = F n ( x ) L n ( x ) .

Closed form expressions, similar to Binet's formula are:

F n ( x ) = α ( x ) n − β ( x ) n α ( x ) − β ( x ) , L n ( x ) = α ( x ) n + β ( x ) n ,

where

α ( x ) = x + x 2 + 4 2 , β ( x ) = x − x 2 + 4 2

are the solutions (in t) of

t 2 − x t − 1 = 0.

A relationship between the Fibonacci polynomials and the standard basis polynomials is given by

x n = F n + 1 ( x ) + ∑ k = 1 ⌊ n / 2 ⌋ ( − 1 ) k [ ( n k ) − ( n k − 1 ) ] F n + 1 − 2 k ( x ) .

For example,

x 4 = F 5 ( x ) − 3 F 3 ( x ) + 2 F 1 ( x ) x 5 = F 6 ( x ) − 4 F 4 ( x ) + 4 F 2 ( x ) x 6 = F 7 ( x ) − 5 F 5 ( x ) + 9 F 3 ( x ) − 5 F 1 ( x ) x 7 = F 8 ( x ) − 6 F 6 ( x ) + 14 F 4 ( x ) − 14 F 2 ( x )

A proof of this fact is given starting from page 5 here.

Combinatorial interpretation

If F(n,k) is the coefficient of xk in Fn(x), so

F n ( x ) = ∑ k = 0 n F ( n , k ) x k ,

then F(n,k) is the number of ways an n−1 by 1 rectangle can be tiled with 2 by 1 dominoes and 1 by 1 squares so that exactly k squares are used. Equivalently, F(n,k) is the number of ways of writing n−1 as an ordered sum involving only 1 and 2, so that 1 is used exactly k times. For example F(6,3)=4 and 5 can be written in 4 ways, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, as a sum involving only 1 and 2 with 1 used 3 times. By counting the number of times 1 and 2 are both used in such a sum, it is evident that F(n,k) is equal to the binomial coefficient

F ( n , k ) = ( n + k − 1 2 k )

when n and k have opposite parity. This gives a way of reading the coefficients from Pascal's triangle as shown on the right.

References

Fibonacci polynomials Wikipedia
(Text) CC BY-SA