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 $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 terme 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}}$

Le polynôme $F_{n}$ est 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

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

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

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fibonacci polynomials » (voir la liste des auteurs).

Voir aussi

Bibliographie

• (en) Dominique Foata et Guo-Niu Han, « Nombres de Fibonacci et polynômes orthogonaux », Leonardo Fibonacci : il tempo, le opere, l’eredit`a scientifica,‎ 1994 (lire en ligne)
• (en) V. E. Hoggatt et Calvin T. Long, « Divisibility properties of generalized Fibonacci Polynomials », Fibonacci Quarterly, vol. 12,‎ 1974, p. 113 (MR 0352034, lire en ligne)
• (en) Paolo Emilio Ricci, « Generalized Lucas polynomials and Fibonacci polynomials », Rivista di Matematica della Università di Parma, vol. 4,‎ 1995, p. 137-146 (MR 1395332)
• (en) Johann Cigler, « q-Fibonacci polynomials », Fibonacci Quarterly, n^o 41,‎ 2003, p. 31-40 (MR 1962279, lire en ligne)

Liens externes

• (en) Eric W. Weisstein, « Fibonacci Polynomial », sur MathWorld
• (en) Eric W. Weisstein, « Lucas Polynomial », sur MathWorld