Polynôme de Fibonacci

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}}}$ ; ${\displaystyle F_{n}}$ est un polynôme 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].

Les coefficients des polynômes de Fibonacci se lisent sur les « diagonales » du triangle de Pascal (montrées en rouge). Les sommes des coefficients forment la suite de Fibonacci.

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.