Polynôme de Fibonacci

Polynôme de Fibonacci

Présentation

Type	Suite de polynômes, suite de Lucas

modifier - modifier le code - modifier Wikidata

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.

Définition

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

Séries génératrices

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

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^[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)}$.

Racines et factorisation des polynômes de Fibonacci

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

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

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

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

1. (en) Arthur T. Benjamin et Jennifer J. Quinn, Proofs that Really Count, Washington, DC, MAA, 2003, 193 p. (ISBN 0-88385-333-7, lire en ligne), « §9.4 Fibonacci and Lucas Polynomial », p. 141.
2. (en) Leonard Carlitz, « Some orthogonal polynomials related to Fibonacci numbers », Fibonacci Quarterly, vol. 4, n^o 1,‎ 1966, p. 43-48 (lire en ligne).
3. (en) Yi Yuan et Wenpeng Zhang, « Some identities involving the Fibonacci Polynomials », Fibonacci Quarterly, vol. 40, n^o 4,‎ 2002, p. 314 (MR 1920571, lire en ligne).
4. (en) Carnegie Mellon Informatics and Mathematics Competition (CMIMC) 2016, exercice 10 (à partir de la page 5).
5. (en) V. E. Hoggatt (en) et Marjorie Bicknell, « Roots of Fibonacci polynomials. », Fibonacci Quarterly, vol. 11,‎ 1973, p. 271-274 (MR 0332645, lire en ligne).
6. (en) Bala Sury, « Trigonometric expressions for Fibonacci and Lucas Numbers », Acta Math. Univ. Comenianae, vol. 79, n^o 2,‎ 2010, p. 199-208 (lire en ligne).

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