title: Polynôme de Fibonacci
text: # Polynôme de Fibonacci
  
  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 nombre 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}}$ ; $F_{n}$ est un polynôme 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
  
  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.
  
  