Polynôme de Fibonacci
# Polynôme de Fibonacci

En mathématiques les polynômes de Fibonacci, nommés ainsi en l'honneur du mathématicien italien Leonardo Fibonacci, sont une suite de polynômes $F_{n}(x)$ généralisant les nombres de Fibonacci, définis d'une manière telle que $F_{n}(1)$ soit égal au n-ième nombre de la suite de Fibonacci. Les polynômes de Lucas généralisent de même les nombres de Lucas.

## Définition

Les polynômes de Fibonacci sont définis par une relation de récurrence linéaire.

    $F_{n}(x)={\begin{cases}0,&{\mbox{si }}n=0\\1,&{\mbox{si }}n=1\\xF_{n-1}(x)+F_{n-2}(x),&{\mbox{si }}n\geq 2\end{cases}}$ ; $F_{n}$ est un polynôme de degré n-1.

Les premiers polynômes de Fibonacci sont :

    $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\,$

Les polynômes de Lucas sont définis par la même récurrence, mais avec des valeurs initiales différentes :

    $L_{n}(x)={\begin{cases}2,&{\mbox{si }}n=0\\x,&{\mbox{si }}n=1\\xL_{n-1}(x)+L_{n-2}(x),&{\mbox{si }}n\geq 2.\end{cases}}$ ; $L_{n}$ est un polynôme de degré n.

Les premiers polynômes de Lucas sont :

    $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.\,$

Les nombres de Fibonacci sont alors calculés en évaluant la valeur du polynôme $F_n$ lorsque x = 1 ; les nombres de Pell sont déterminés en évaluant $F_n$ lorsque x = 2. Enfin, les nombres de Lucas sont obtenus en évaluant $L_n$ en 1.

Ces suites de polynômes sont des suites de Lucas associées : on a

    $F_{n}(x)=U_{n}(x,-1),\,$
    $L_{n}(x)=V_{n}(x,-1).\,$

## Séries génératrices

La série génératrice pour les polynômes de Fibonacci est :

    $\sum _{n=0}^{\infty }F_{n}(x)t^{n}={\frac {t}{1-xt-t^{2}}}.$

De même, la série génératrice des polynômes de Lucas est :

    $\sum _{n=0}^{\infty }L_{n}(x)t^{n}={\frac {2-xt}{1-xt-t^{2}}}.$

## Relations remarquables

En tant que cas particuliers de suites de Lucas, ces polynômes vérifient de nombreuses identités.

Ils peuvent être définis pour des indices négatifs par

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

On a également :

    $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).\,$

Des expressions analogues à la formule de Binet existent :

    $F_{n}(x)={\frac {\alpha (x)^{n}-\beta (x)^{n}}{\alpha (x)-\beta (x)}},\,L_{n}(x)=\alpha (x)^{n}+\beta (x)^{n},$

où

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

sont les solutions (en t) de

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

Les puissances de x s'expriment comme combinaison des polynômes de Fibonacci par

    $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).$

Par exemple,

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

## Racines et factorisation des polynômes de Fibonacci

Posant $x=2\mathrm {i} \cosh z=\mathrm {i} \left(\mathrm {e} ^{z}+\mathrm {e} ^{-z}\right)$, on vérifie qu'avec les notations précédentes, $\alpha \left(x\right)=\left(x+{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{z}$, $\beta \left(x\right)=\left(x-{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{-z}$, et donc que $F_{n}\left(x\right)=\mathrm {i} ^{n-1}{\frac {\mathrm {e} ^{nz}-\mathrm {e} ^{-nz}}{\mathrm {e} ^{z}-\mathrm {e} ^{-z}}}$, qui ne s'annule que pour $z=\mathrm {i} \,k\pi /n$ ; ainsi les racines de $F_{n}$ sont les imaginaires purs $2\mathrm {i} \cos {(k\pi /n)}$. On en déduit la factorisation des $F_{n}\left(x\right)$ :

    $F_{2n}\left(x\right)=x\prod _{1\leq k\leq n-1}x^{2}+4\cos ^{2}\left({\frac {k\pi }{n}}\right)$ et
    $F_{2n+1}\left(x\right)=\prod _{1\leq k\leq n}x^{2}+4\cos ^{2}\left({\frac {2k\pi }{2n+1}}\right)$,

puis, prenant $x=1$, une expression trigonométrique des nombres de Fibonacci :

    ${\mathcal {F}}_{n}=\prod _{1\leq k\leq (n-1)/2}1+4\cos ^{2}\left({\frac {k\pi }{n}}\right)=\prod _{1\leq k\leq (n-1)/2}3+2\cos \left({\frac {2k\pi }{n}}\right)$ ;

des formules analogues peuvent être obtenues pour les polynômes de Lucas.

## Interprétation combinatoire

Si F(n,k) est le coefficient de $x^k$ dans $F_n(x),$ c'est-à-dire que

    $F_{n}(x)=\sum _{k=0}^{n}F(n,k)x^{k},\,$

alors F(n,k) est le nombre de façons dont on peut paver une bande de n−1 carrés avec des dominos (des rectangles $2\times 1$) et exactement k carrés unité. De façon équivalente, F(n,k) est le nombre de façons d'écrire n−1 comme une somme ordonnée de 1 et de 2, avec exactement k apparitions de 1. Par exemple, F(6,3)=4 et 5 peut s'écrire de 4 façons, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, comme somme de 1 et de 2 avec exactement trois 1. Déterminant la position des 1 dans une telle somme, il devient alors évident que F(n,k) est égal au coefficient binomial

    $F(n,k)={\binom {\tfrac {n+k-1}{2}}{k}}$

où n et k sont de parité opposée, ce qui permet de lire ces coefficients dans le triangle de Pascal, comme montré ci-dessus.

