title: Suite de Lucas
text: # Suite de Lucas
  
  En mathématiques, les suites de Lucas U(P, Q) et V(P, Q) associées à deux entiers P et Q sont deux suites récurrentes linéaires d'ordre 2 à valeurs entières qui généralisent respectivement la suite de Fibonacci et celle de Fibonacci-Lucas, correspondant aux valeurs P = 1 et Q = –1.
  
  Elles doivent leur nom au mathématicien français Édouard Lucas.
  
  ## Définition par récurrence
  
  Soient P et Q deux entiers non nuls tels que
  
      $\Delta =P^{2}-4Q\neq 0$
  
  (pour éviter les cas dégénérés).
  
  Les suites de Lucas U(P, Q) et V(P, Q) sont définies par les relations de récurrence linéaire
  
      $U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n}(P,Q)=P.U_{n-1}(P,Q)-Q.U_{n-2}(P,Q){\mbox{ pour }}n\geqslant 2$
  
  et
  
      $V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n}(P,Q)=P.V_{n-1}(P,Q)-Q.V_{n-2}(P,Q){\mbox{ pour }}n\geqslant 2.$
  
  ## Terme général
  
  Notons $\delta$ l'une des deux racines carrées de Δ (éventuellement dans ℂ).
  
  Puisque Δ ≠ 0, le polynôme caractéristique associé à la récurrence $X^2$ – PX + Q possède deux racines distinctes
  
      $a={\frac {P+\delta }{2}}\quad {\rm {et}}\quad b={\frac {P-\delta }{2}}.$
  
  Alors U(P, Q) et V(P, Q) peuvent aussi être définies en fonction de a et b par l'analogue suivant de la formule de Binet :
  
      $U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\delta }}\quad {\rm {et}}\quad V_{n}(P,Q)=a^{n}+b^{n},$
  
  dont on peut tirer les relations
  
      $a^{n}={\frac {V_{n}+U_{n}\delta }{2}}\quad {\rm {et}}\quad b^{n}={\frac {V_{n}-U_{n}\delta }{2}}.$
  
  ## Autres relations
  
  Les nombres dans les suites de Lucas satisfont à de nombreuses relations, qui généralisent celles entre les nombres de Fibonacci et les nombres de Lucas. Par exemple :
  
      $(*)\quad U_{n}U_{m+r}-U_{r}U_{m+n}=Q^{r}U_{n-r}U_{m}$
      $(**)\quad U_{m+n}=$$^,$ $U_{n}U_{m+1}-QU_{n-1}U_{m}={U_{n}V_{m}+U_{m}V_{n} \over 2}$ et
      $V_{m+n}=V_{m}V_{n}-Q^{m}V_{n-m}={\Delta U_{m}U_{n}+V_{m}V_{n} \over 2},$
  
  en particulier
  
      $U_{n+1}={PU_{n}+V_{n} \over 2}=V_{n}+QU_{n-1},\qquad V_{n+1}={\Delta U_{n}+PV_{n} \over 2}=\Delta U_{n}+QV_{n-1}$
  
  et
  
      $U_{2n}=U_{n}V_{n},\qquad V_{2n}=V_{n}^{2}-2Q^{n}.$
  
  ## Divisibilité
  
  De la deuxième identité ci-dessus, (**) $U_{m+n}$ = $U_nU_{m+1}$ – $QU_{n–1}U_m,$ on déduit immédiatement (par récurrence sur k) que $U_{nk}$ est toujours un multiple de $U_n$ : on dit que la suite U(P, Q) est à divisibilité faible.
  
  Plaçons-nous dans le cas non dégénéré et supposons $k>0$ et, pour alléger l'écriture, $U_{n}\neq 0$ (dans le cas $U_{n}=0$, il suffit d'écrire les égalités correspondantes sans division par $U_{n}$).
  
      ${\begin{aligned}{\frac {U_{nk}}{U_{n}}}&={\frac {a^{nk}-b^{nk}}{a^{n}-b^{n}}}=\sum _{j=0}^{k-1}a^{n(k-1-j)}b^{nj}\\&=(a^{n(k-1)}+b^{n(k-1)})+(a^{n(k-2)}b^{n}+b^{n(k-2)}a^{n})+(a^{n(k-3)}b^{2n}+b^{n(k-3)}a^{2n})+\ldots \\&=(a^{n(k-1)}+b^{n(k-1)})+Q^{n}(a^{n(k-3)}+b^{n(k-3)})+Q^{2n}(a^{n(k-5)}+b^{n(k-5)})+\ldots \\&=V_{n(k-1)}+Q^{n}V_{n(k-3)}+Q^{2n}V_{n(k-5)}+\ldots \in \mathbb {Z} .\end{aligned}}$
  
  Pour qu'elle soit même à divisibilité forte, c'est-à-dire que $pgcd(U_i,$ $U_j)$ soit non seulement divisible par $U_{pgcd(i,j)}$ mais égal (au signe près), il faut et il suffit que P et Q soient premiers entre $eux^,.$
  
  Si la suite est à divisibilité forte alors 1 = $U_1$ = $pgcd(U_2,$ $U_3)$ = pgcd(P, $P^2$ – Q) = pgcd(P, Q).
  
  Réciproquement, supposons que pgcd(P, Q) = 1 et montrons d'abord par récurrence que pour tout n ≥ 1, $U_n$ est premier avec Q.
  
  L'initialisation est immédiate, et l'hérédité se déduit (grâce au lemme de Gauss) de $pgcd(U_{n+1},$ Q) = $pgcd(PU_n,$ Q) et de l'hypothèse.
  
  On déduit ensuite de cette propriété, jointe à l'identité $U_nU_{r+1}$ – $U_rU_{n+1}$ = $Q^rU_{n–r},$ que $pgcd(U_n,$ $U_r)$ divise $pgcd(U_{n–r},$ $U_r)$ pour 0 < r < n donc (par anthyphérèse) $pgcd(U_i,$ $U_j)$ divise $U_{pgcd(i,j)}.$ La divisibilité forte s'ensuit.
  
  ## Cas particuliers
  
      $U(1,-1)$ est la suite de Fibonacci et $V(1,-1)$ la suite de Fibonacci-Lucas.
      $U(2,-1)$ est la suite de Pell et $V(2,-1)$ la suite de Pell-Lucas.
  
  Plus généralement, $U_{n}(P,-1)$ et $V_{n}(P,-1)$ sont les valeurs en P du n-ième polynôme de Fibonacci et du n-ième polynôme de Lucas.
  
  $U(a+b,ab)=\left({\frac {a^{n}-b^{n}}{a-b}}\right)$ donne comme cas particulier $U(3,2)=(2^{n}-1)$ qui est la suite des nombres de Mersenne et plus généralement, $U(b+1,b)$ qui est la suite des répunits en base b.
  
      $U(1,-2)$ est la suite de Jacobstahl et $V(1,-2)$ la suite de Jacobsthal-Lucas.
      $U(1,1)=\left({\frac {2\sin {\frac {n\pi }{3}}}{\sqrt {3}}}\right)=(0,1,1,0,-1,-1,0,...)$, $V(1,1)=\left(2\cos {\frac {n\pi }{3}}\right)=(2,1,-1,-2,-1,1,2,...)$.
      $S_{k}:=V_{2^{k}}({\sqrt {2}},-1)$ (k ≥ 1) est la suite qui intervient dans le test de primalité de Lucas-Lehmer pour les nombres de Mersenne : $S_1$ = $V_2$ = 4 et $S_{k+1}$ = $S_k^2$ – 2.
  