Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fibonacci polynomials
Summary
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.
These Fibonacci polynomials are defined by a recurrence relation:
The Lucas polynomials use the same recurrence with different starting values:
They can be defined for negative indices by
The Fibonacci polynomials form a sequence of orthogonal polynomials with and .
The first few Fibonacci polynomials are:
The first few Lucas polynomials are:
The degree of Fn is n − 1 and the degree of Ln is n.
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 ordinary generating functions for the sequences are:
The polynomials can be expressed in terms of Lucas sequences as
They can also be expressed in terms of Chebyshev polynomials and as
where is the imaginary unit.
Lucas sequence
As particular cases of Lucas sequences, Fibonacci polynomials satisfy a number of identities, such as
Closed form expressions, similar to Binet's formula are:
where
are the solutions (in t) of
For Lucas Polynomials n > 0, we have
A relationship between the Fibonacci polynomials and the standard basis polynomials is given by
For example,
If F(n,k) is the coefficient of xk in Fn(x), namely
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
This gives a way of reading the coefficients from Pascal's triangle as shown on the right.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.