Polynôme de Fibonacci

Polynôme de Fibonacci

Présentation

Type	Suite de polynômes, suite de Lucas

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 ${\displaystyle F_{n}(x)}$ généralisant les nombres de Fibonacci, définis d'une manière telle que ${\displaystyle F_{n}(1)}$ soit égal au n-ième terme de la suite de Fibonacci. Les polynômes de Lucas généralisent de même les nombres de Lucas.

Les polynômes de Fibonacci sont définis par une relation de récurrence linéaire^[1] :

${\displaystyle 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}}}$

Le polynôme ${\displaystyle F_{n}}$ est de degré n-1.

Les premiers polynômes de Fibonacci sont :

${\displaystyle F_{0}(x)=0\,}$;

${\displaystyle F_{1}(x)=1\,}$;

${\displaystyle F_{2}(x)=x\,}$;

${\displaystyle F_{3}(x)=x^{2}+1\,}$;

${\displaystyle F_{4}(x)=x^{3}+2x\,}$;

${\displaystyle F_{5}(x)=x^{4}+3x^{2}+1\,}$;

${\displaystyle 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 :

${\displaystyle 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}}}$ ; ${\displaystyle L_{n}}$ est un polynôme de degré n.

Les premiers polynômes de Lucas sont :

${\displaystyle L_{0}(x)=2\,}$

${\displaystyle L_{1}(x)=x\,}$;

${\displaystyle L_{2}(x)=x^{2}+2\,}$;

${\displaystyle L_{3}(x)=x^{3}+3x\,}$;

${\displaystyle L_{4}(x)=x^{4}+4x^{2}+2\,}$;

${\displaystyle L_{5}(x)=x^{5}+5x^{3}+5x\,}$;

${\displaystyle 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

${\displaystyle F_{n}(x)=U_{n}(x,-1),\,}$

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

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

${\displaystyle \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 :

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

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^[3]

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

On a également^[3] :

${\displaystyle F_{m+n}(x)=F_{m+1}(x)F_{n}(x)+F_{m}(x)F_{n-1}(x)\,}$

${\displaystyle L_{m+n}(x)=L_{m}(x)L_{n}(x)-(-1)^{n}L_{m-n}(x)\,}$

${\displaystyle F_{n+1}(x)F_{n-1}(x)-F_{n}(x)^{2}=(-1)^{n}\,}$

${\displaystyle F_{2n}(x)=F_{n}(x)L_{n}(x).\,}$

Des expressions analogues à la formule de Binet existent^[3] :

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

où

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

sont les solutions (en t) de

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

Les puissances de x s'expriment comme combinaison des polynômes de Fibonacci par^[4]

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

${\displaystyle x^{4}=F_{5}(x)-3F_{3}(x)+2F_{1}(x)\,}$;

${\displaystyle x^{5}=F_{6}(x)-4F_{4}(x)+4F_{2}(x)\,}$;

${\displaystyle x^{6}=F_{7}(x)-5F_{5}(x)+9F_{3}(x)-5F_{1}(x)\,}$;

${\displaystyle x^{7}=F_{8}(x)-6F_{6}(x)+14F_{4}(x)-14F_{2}(x)}$.

Posant ${\displaystyle 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, ${\displaystyle \alpha \left(x\right)=\left(x+{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{z}}$, ${\displaystyle \beta \left(x\right)=\left(x-{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{-z}}$, et donc que ${\displaystyle 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 ${\displaystyle z=\mathrm {i} \,k\pi /n}$ ; ainsi les racines de ${\displaystyle F_{n}}$ sont les imaginaires purs ${\displaystyle 2\mathrm {i} \cos {(k\pi /n)}}$^[5]. On en déduit la factorisation des ${\displaystyle F_{n}\left(x\right)}$ :

${\displaystyle 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

${\displaystyle 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 ${\displaystyle x=1}$, une expression trigonométrique des nombres de Fibonacci^[6] :

${\displaystyle {\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^[5].

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

${\displaystyle 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 ${\displaystyle 2\times 1}$) et exactement k carrés unité^[1]. 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

${\displaystyle 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.