Suite de Lucas

Soient P et Q deux entiers non nuls tels que

${\displaystyle \Delta =P^{2}-4Q\neq 0}$

(pour éviter les cas dégénérés)^[2].

Les suites de Lucas U(P, Q) et V(P, Q) sont définies par les relations de récurrence linéaire

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

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

Notons ${\displaystyle \delta }$ l'une des deux racines carrées de Δ (éventuellement dans ℂ).

Puisque Δ ≠ 0, le polynôme caractéristique associé à la récurrence X² – PX + Q possède deux racines distinctes

${\displaystyle 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^[a] :

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

${\displaystyle a^{n}={\frac {V_{n}+U_{n}\delta }{2}}\quad {\rm {et}}\quad b^{n}={\frac {V_{n}-U_{n}\delta }{2}}.}$

Les nombres dans les suites de Lucas satisfont à de nombreuses relations^[3], qui généralisent celles entre les nombres de Fibonacci et les nombres de Lucas. Par exemple^[b] :

${\displaystyle (*)\quad U_{n}U_{m+r}-U_{r}U_{m+n}=Q^{r}U_{n-r}U_{m}}$^[c]

${\displaystyle (**)\quad U_{m+n}=}$^[d],[4] ${\displaystyle U_{n}U_{m+1}-QU_{n-1}U_{m}={U_{n}V_{m}+U_{m}V_{n} \over 2}}$ et

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

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

${\displaystyle U_{2n}=U_{n}V_{n},\qquad V_{2n}=V_{n}^{2}-2Q^{n}.}$

De la deuxième identité ci-dessus, (**) U_m+n = U_nU_m+1 – QU_n–1U_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.

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^[b],[5].

${\displaystyle U(1,-1)}$ est la suite de Fibonacci et ${\displaystyle V(1,-1)}$ la suite de Fibonacci-Lucas.

${\displaystyle U(2,-1)}$ est la suite de Pell et ${\displaystyle V(2,-1)}$ la suite de Pell-Lucas.

Plus généralement, ${\displaystyle U_{n}(P,-1)}$ et ${\displaystyle 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.

${\displaystyle U(a+b,ab)=\left({\frac {a^{n}-b^{n}}{a-b}}\right)}$ donne comme cas particulier ${\displaystyle U(3,2)=(2^{n}-1)}$ qui est la suite des nombres de Mersenne et plus généralement, ${\displaystyle U(b+1,b)}$ qui est la suite des répunits en base b.

${\displaystyle U(1,-2)}$ est la suite de Jacobstahl et ${\displaystyle V(1,-2)}$ la suite de Jacobsthal-Lucas.

${\displaystyle U(1,1)=\left({\frac {2\sin {\frac {n\pi }{3}}}{\sqrt {3}}}\right)=(0,1,1,0,-1,-1,0,...)}$, ${\displaystyle V(1,1)=\left(2\cos {\frac {n\pi }{3}}\right)=(2,1,-1,-2,-1,1,2,...)}$.

${\displaystyle 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₁ = V₂ = 4 et S_k+1 = S_k² – 2.