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 ) {\displaystyle F_{n}(x)} généralisant les nombres de Fibonacci , définis d'une manière telle que F n ( 1 ) {\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] :
F n ( x ) = { 0 , si n = 0 ; 1 , si n = 1 ; x F n − 1 ( x ) + F n − 2 ( x ) , si n ≥ 2. {\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 F n {\displaystyle F_{n}} est de degré n -1.
Les premiers polynômes de Fibonacci sont :
F 0 ( x ) = 0 {\displaystyle F_{0}(x)=0\,} ; F 1 ( x ) = 1 {\displaystyle F_{1}(x)=1\,} ; F 2 ( x ) = x {\displaystyle F_{2}(x)=x\,} ; F 3 ( x ) = x 2 + 1 {\displaystyle F_{3}(x)=x^{2}+1\,} ; F 4 ( x ) = x 3 + 2 x {\displaystyle F_{4}(x)=x^{3}+2x\,} ; F 5 ( x ) = x 4 + 3 x 2 + 1 {\displaystyle F_{5}(x)=x^{4}+3x^{2}+1\,} ; F 6 ( x ) = x 5 + 4 x 3 + 3 x {\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 :
L n ( x ) = { 2 , si n = 0 x , si n = 1 x L n − 1 ( x ) + L n − 2 ( x ) , si n ≥ 2. {\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}}} ; L n {\displaystyle L_{n}} est un polynôme de degré n . Les premiers polynômes de Lucas sont :
L 0 ( x ) = 2 {\displaystyle L_{0}(x)=2\,} L 1 ( x ) = x {\displaystyle L_{1}(x)=x\,} ; L 2 ( x ) = x 2 + 2 {\displaystyle L_{2}(x)=x^{2}+2\,} ; L 3 ( x ) = x 3 + 3 x {\displaystyle L_{3}(x)=x^{3}+3x\,} ; L 4 ( x ) = x 4 + 4 x 2 + 2 {\displaystyle L_{4}(x)=x^{4}+4x^{2}+2\,} ; L 5 ( x ) = x 5 + 5 x 3 + 5 x {\displaystyle L_{5}(x)=x^{5}+5x^{3}+5x\,} ; L 6 ( x ) = x 6 + 6 x 4 + 9 x 2 + 2 {\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
F n ( x ) = U n ( x , − 1 ) , {\displaystyle F_{n}(x)=U_{n}(x,-1),\,} L n ( x ) = V 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] :
∑ n = 0 ∞ F n ( x ) t n = t 1 − x t − t 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 :
∑ n = 0 ∞ L n ( x ) t n = 2 − x t 1 − x t − t 2 . {\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]
F − n ( x ) = ( − 1 ) n − 1 F n ( x ) , L − n ( x ) = ( − 1 ) n L n ( x ) . {\displaystyle F_{-n}(x)=(-1)^{n-1}F_{n}(x),\,L_{-n}(x)=(-1)^{n}L_{n}(x).} On a également[ 3] :
F m + n ( x ) = F m + 1 ( x ) F n ( x ) + F m ( x ) F n − 1 ( x ) {\displaystyle 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 ) {\displaystyle 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 {\displaystyle F_{n+1}(x)F_{n-1}(x)-F_{n}(x)^{2}=(-1)^{n}\,} F 2 n ( x ) = F n ( x ) L n ( x ) . {\displaystyle F_{2n}(x)=F_{n}(x)L_{n}(x).\,} Des expressions analogues à la formule de Binet existent[ 3] :
F n ( x ) = α ( x ) n − β ( x ) n α ( x ) − β ( x ) , L n ( x ) = α ( x ) n + β ( x ) n , {\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ù
α ( x ) = x + x 2 + 4 2 , β ( x ) = x − x 2 + 4 2 {\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
t 2 − x t − 1 = 0. {\displaystyle t^{2}-xt-1=0.\,} Les puissances de x s'expriment comme combinaison des polynômes de Fibonacci par[ 4]
x n = F n + 1 ( x ) + ∑ k = 1 ⌊ n / 2 ⌋ ( − 1 ) k [ ( n k ) − ( n k − 1 ) ] F n + 1 − 2 k ( x ) . {\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,
x 4 = F 5 ( x ) − 3 F 3 ( x ) + 2 F 1 ( x ) {\displaystyle x^{4}=F_{5}(x)-3F_{3}(x)+2F_{1}(x)\,} ; x 5 = F 6 ( x ) − 4 F 4 ( x ) + 4 F 2 ( x ) {\displaystyle x^{5}=F_{6}(x)-4F_{4}(x)+4F_{2}(x)\,} ; x 6 = F 7 ( x ) − 5 F 5 ( x ) + 9 F 3 ( x ) − 5 F 1 ( x ) {\displaystyle x^{6}=F_{7}(x)-5F_{5}(x)+9F_{3}(x)-5F_{1}(x)\,} ; x 7 = F 8 ( x ) − 6 F 6 ( x ) + 14 F 4 ( x ) − 14 F 2 ( x ) {\displaystyle x^{7}=F_{8}(x)-6F_{6}(x)+14F_{4}(x)-14F_{2}(x)} . Racines et factorisation des polynômes de Fibonacci [ modifier | modifier le code ] Posant x = 2 i cosh z = i ( e z + e − z ) {\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, α ( x ) = ( x + x 2 + 4 ) / 2 = i e z {\displaystyle \alpha \left(x\right)=\left(x+{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{z}} , β ( x ) = ( x − x 2 + 4 ) / 2 = i e − z {\displaystyle \beta \left(x\right)=\left(x-{\sqrt {x^{2}+4}}\right)/2=\mathrm {i} \,\mathrm {e} ^{-z}} , et donc que F n ( x ) = i n − 1 e n z − e − n z e z − e − z {\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 z = i k π / n {\displaystyle z=\mathrm {i} \,k\pi /n} ; ainsi les racines de F n {\displaystyle F_{n}} sont les imaginaires purs 2 i cos ( k π / n ) {\displaystyle 2\mathrm {i} \cos {(k\pi /n)}} [ 5] . On en déduit la factorisation des F n ( x ) {\displaystyle F_{n}\left(x\right)} :
F 2 n ( x ) = x ∏ 1 ≤ k ≤ n − 1 x 2 + 4 cos 2 ( k π n ) {\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 F 2 n + 1 ( x ) = ∏ 1 ≤ k ≤ n x 2 + 4 cos 2 ( 2 k π 2 n + 1 ) {\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 x = 1 {\displaystyle x=1} , une expression trigonométrique des nombres de Fibonacci[ 6] :
F n = ∏ 1 ≤ k ≤ ( n − 1 ) / 2 1 + 4 cos 2 ( k π n ) = ∏ 1 ≤ k ≤ ( n − 1 ) / 2 3 + 2 cos ( 2 k π n ) {\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 xk dans Fn (x ), c'est-à-dire que
F n ( x ) = ∑ k = 0 n F ( n , k ) x k , {\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 2 × 1 {\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
F ( n , k ) = ( n + k − 1 2 k ) {\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.
↑ a et b (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 . ↑ (en) Leonard Carlitz , « Some orthogonal polynomials related to Fibonacci numbers », Fibonacci Quarterly , vol. 4, no 1, 1966 , p. 43-48 (lire en ligne ) . ↑ a b et c (en) Yi Yuan et Wenpeng Zhang , « Some identities involving the Fibonacci Polynomials », Fibonacci Quarterly , vol. 40, no 4, 2002 , p. 314 (MR 1920571 , lire en ligne ) . ↑ (en) Carnegie Mellon Informatics and Mathematics Competition (CMIMC) 2016 , exercice 10 (à partir de la page 5). ↑ a et b (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 ) . ↑ (en) Bala Sury, « Trigonometric expressions for Fibonacci and Lucas Numbers », Acta Math. Univ. Comenianae , vol. 79, no 2, 2010 , p. 199-208 (lire en ligne ) . (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 , no 41, 2003 , p. 31-40 (MR 1962279 , lire en ligne )