# 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.

## Definition

These Fibonacci polynomials are defined by a recurrence relation:
    $F_{n}(x)={\begin{cases}0,&{\mbox{if }}n=0\\1,&{\mbox{if }}n=1\\xF_{n-1}(x)+F_{n-2}(x),&{\mbox{if }}n\geq 2\end{cases}}$
The Lucas polynomials use the same recurrence with different starting values:
    $L_{n}(x)={\begin{cases}2,&{\mbox{if }}n=0\\x,&{\mbox{if }}n=1\\xL_{n-1}(x)+L_{n-2}(x),&{\mbox{if }}n\geq 2.\end{cases}}$
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).$
The Fibonacci polynomials form a sequence of orthogonal polynomials with $A_{n}=C_{n}=1$ and $B_{n}=0$.

## Examples

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}+2x\,$
    $F_{5}(x)=x^{4}+3x^{2}+1\,$
    $F_{6}(x)=x^{5}+4x^{3}+3x\,$
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}+3x\,$
    $L_{4}(x)=x^{4}+4x^{2}+2\,$
    $L_{5}(x)=x^{5}+5x^{3}+5x\,$
    $L_{6}(x)=x^{6}+6x^{4}+9x^{2}+2.\,$

## Properties

* The degree of F$_n$ is n − 1 and the degree of L$_n$ is n.
* The Fibonacci and Lucas numbers are recovered by evaluating the polynomials at x = 1; Pell numbers are recovered by evaluating F$_n$ at x = 2.
* The ordinary generating functions for the sequences are:
    $\sum _{n=0}^{\infty }F_{n}(x)t^{n}={\frac {t}{1-xt-t^{2}}}$
    $\sum _{n=0}^{\infty }L_{n}(x)t^{n}={\frac {2-xt}{1-xt-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).\,$
* They can also be expressed in terms of Chebyshev polynomials ${\mathcal {T}}_{n}(x)$ and ${\mathcal {U}}_{n}(x)$ as
    $F_{n}(x)=i^{n-1}\cdot {\mathcal {U}}_{n-1}({\tfrac {-ix}{2}}),\,$
    $L_{n}(x)=2\cdot i^{n}\cdot {\mathcal {T}}_{n}({\tfrac {-ix}{2}}),\,$
    where $i$ is the imaginary unit.

## Identities

As particular cases of Lucas sequences, Fibonacci polynomials satisfy a number of identities, such as
    $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_{2n}(x)=F_{n}(x)L_{n}(x).\,$
Closed form expressions, similar to Binet's formula are:
    $F_{n}(x)={\frac {\alpha (x)^{n}-\beta (x)^{n}}{\alpha (x)-\beta (x)}},\,L_{n}(x)=\alpha (x)^{n}+\beta (x)^{n},$
where
    $\alpha (x)={\frac {x+{\sqrt {x^{2}+4}}}{2}},\,\beta (x)={\frac {x-{\sqrt {x^{2}+4}}}{2}}$
are the solutions (in t) of
    $t^{2}-xt-1=0.\,$
For Lucas Polynomials n > 0, we have
    $L_{n}(x)=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n}{n-k}}{\binom {n-k}{k}}x^{n-2k}.$
A relationship between the Fibonacci polynomials and the standard basis polynomials is given by
    $x^{n}=F_{n+1}(x)+\sum _{k=1}^{\lfloor n/2\rfloor }(-1)^{k}\left[{\binom {n}{k}}-{\binom {n}{k-1}}\right]F_{n+1-2k}(x).$
For example,
    $x^{4}=F_{5}(x)-3F_{3}(x)+2F_{1}(x)\,$
    $x^{5}=F_{6}(x)-4F_{4}(x)+5F_{2}(x)\,$
    $x^{6}=F_{7}(x)-5F_{5}(x)+9F_{3}(x)-5F_{1}(x)\,$
    $x^{7}=F_{8}(x)-6F_{6}(x)+14F_{4}(x)-14F_{2}(x)\,$

## Combinatorial interpretation

If F(n,k) is the coefficient of x$^k$ in F$_n$(x), namely
    $F_{n}(x)=\sum _{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)={\begin{cases}\displaystyle {\binom {{\frac {1}{2}}(n+k-1)}{k}}&{\text{if }}n\not \equiv k{\pmod {2}},\\[12pt]0&{\text{else}}.\end{cases}}$
This gives a way of reading the coefficients from Pascal's triangle as shown on the right.