### Fibonacci polynomial

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\left(x\right)= \begin\left\{cases\right\}$

0, & \mbox{if } n = 0\\ 1, & \mbox{if } n = 1\\ x F_{n - 1}(x) + F_{n - 2}(x),& \mbox{if } n \geq 2 \end{cases}

The first few Fibonacci polynomials are:

$F_0\left(x\right)=0 \,$
$F_1\left(x\right)=1 \,$
$F_2\left(x\right)=x \,$
$F_3\left(x\right)=x^2+1 \,$
$F_4\left(x\right)=x^3+2x \,$
$F_5\left(x\right)=x^4+3x^2+1 \,$
$F_6\left(x\right)=x^5+4x^3+3x \,$

The Lucas polynomials use the same recurrence with different starting values: $L_n\left(x\right) = \begin\left\{cases\right\} 2, & \mbox\left\{if \right\} n = 0 \\ x, & \mbox\left\{if \right\} n = 1 \\ x L_\left\{n - 1\right\}\left(x\right) + L_\left\{n - 2\right\}\left(x\right), & \mbox\left\{if \right\} n \geq 2. \end\left\{cases\right\}$

The first few Lucas polynomials are:

$L_0\left(x\right)=2 \,$
$L_1\left(x\right)=x \,$
$L_2\left(x\right)=x^2+2 \,$
$L_3\left(x\right)=x^3+3x \,$
$L_4\left(x\right)=x^4+4x^2+2 \,$
$L_5\left(x\right)=x^5+5x^3+5x \,$
$L_6\left(x\right)=x^6+6x^4+9x^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:

$\sum_\left\{n=0\right\}^\infty F_n\left(x\right) t^n = \frac\left\{t\right\}\left\{1-xt-t^2\right\}.$
$\sum_\left\{n=0\right\}^\infty L_n\left(x\right) t^n = \frac\left\{2-xt\right\}\left\{1-xt-t^2\right\}.$

The polynomials can be expressed in terms of Lucas sequences as

$F_n\left(x\right) = U_n\left(x,-1\right),\,$
$L_n\left(x\right) = V_n\left(x,-1\right).\,$

## Identities

Main article: Lucas sequence

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

First, they can be defined for negative indices by

$F_\left\{-n\right\}\left(x\right)=\left(-1\right)^\left\{n-1\right\}F_\left\{n\right\}\left(x\right),\,L_\left\{-n\right\}\left(x\right)=\left(-1\right)^nL_\left\{n\right\}\left(x\right).$

Other identities include:

$F_\left\{m+n\right\}\left(x\right)=F_\left\{m+1\right\}\left(x\right)F_n\left(x\right)+F_m\left(x\right)F_\left\{n-1\right\}\left(x\right)\,$
$L_\left\{m+n\right\}\left(x\right)=L_m\left(x\right)L_n\left(x\right)-\left(-1\right)^nL_\left\{m-n\right\}\left(x\right)\,$
$F_\left\{n+1\right\}\left(x\right)F_\left\{n-1\right\}\left(x\right)- F_n\left(x\right)^2=\left(-1\right)^n\,$
$F_\left\{2n\right\}\left(x\right)=F_n\left(x\right)L_n\left(x\right).\,$

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

$F_n\left(x\right)=\frac\left\{\alpha\left(x\right)^n-\beta\left(x\right)^n\right\}\left\{\alpha\left(x\right)-\beta\left(x\right)\right\},\,L_n\left(x\right)=\alpha\left(x\right)^n+\beta\left(x\right)^n,$

where

$\alpha\left(x\right)=\frac\left\{x+\sqrt\left\{x^2+4\right\}\right\}\left\{2\right\},\,\beta\left(x\right)=\frac\left\{x-\sqrt\left\{x^2+4\right\}\right\}\left\{2\right\}$

are the solutions (in t) of

$t^2-xt-1=0.\,$

## Combinatorial interpretation

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

$F_n\left(x\right)=\sum_\left\{k=0\right\}^n F\left(n,k\right)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\left(n,k\right)=\binom\left\{\tfrac\left\{n+k-1\right\}\left\{2\right\}\right\}\left\{k\right\}$

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