Suite de Lucas

En mathématiques, les suites de Lucas Modèle:Math et Modèle:Math associées à deux entiers Modèle:Math et Modèle:Math sont deux suites récurrentes linéaires d'ordre Modèle:Math à valeurs entières qui généralisent respectivement la suite de Fibonacci et celle de Fibonacci-Lucas, correspondant aux valeurs Modèle:Math et Modèle:Math.

Elles doivent leur nom au mathématicien français Édouard Lucas.

Définition par récurrence

Soient Modèle:Math et Modèle:Math deux entiers non nuls tels que

$\mathrm{\Delta }=P^2-4Q\ne 0$

(pour éviter les cas dégénérés).

Les suites de Lucas Modèle:Math et Modèle:Math sont définies par les relations de récurrence linéaire

$U_0(P,Q)=0,U_1(P,Q)=1,U_n(P,Q)=P.U_{n-1}(P,Q)-Q.U_{n-2}(P,Q)\text{ pour }n⩾2$

et

$V_0(P,Q)=2,V_1(P,Q)=P,V_n(P,Q)=P.V_{n-1}(P,Q)-Q.V_{n-2}(P,Q)\text{ pour }n⩾2.$

Terme général

Notons $\delta$ l'une des deux racines carrées de Modèle:Math (éventuellement dans ℂ).

Puisque Modèle:Math, le polynôme caractéristique associé à la récurrence Modèle:Math possède deux racines distinctes

$a=\frac{P+\delta }{2}\mathrm{e}\mathrm{t}b=\frac{P-\delta }{2}.$

Alors Modèle:Math et Modèle:Math peuvent aussi être définies en fonction de Modèle:Math et Modèle:Math 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 }\mathrm{e}\mathrm{t}{V}_n(P,Q)=a^n+b^n,$

dont on peut tirer les relations

$a^n=\frac{V_n+U_n\delta }{2}\mathrm{e}\mathrm{t}{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 : Modèle:Ancre

$(*)U_n{U}_{m+r}-U_r{U}_{m+n}=Q^r{U}_{n-r}{U}_m$

$(**)U_{m+n}=$Modèle:, $U_n{U}_{m+1}-Q{U}_{n-1}{U}_m=\frac{U_n{V}_m+U_m{V}_n}{2}$ et

$V_{m+n}=V_m{V}_n-Q^m{V}_{n-m}=\frac{\mathrm{\Delta }{U}_m{U}_n+V_m{V}_n}{2},$

en particulier

$U_{n+1}=\frac{P{U}_n+V_n}{2}=V_n+Q{U}_{n-1},V_{n+1}=\frac{\mathrm{\Delta }{U}_n+P{V}_n}{2}=\mathrm{\Delta }{U}_n+Q{V}_{n-1}$

et

$U_{2n}=U_n{V}_n,V_{2n}=V_n^2-2Q^n.$

Divisibilité

De la deuxième identité ci-dessus, (**) UModèle:Ind = UModèle:IndUModèle:Ind – QUModèle:IndUModèle:Ind, on déduit immédiatement (par récurrence sur k) que UModèle:Ind est toujours un multiple de UModèle:Ind : on dit que la suite U(P, Q) est à divisibilité faible. Modèle:Démonstration

Pour qu'elle soit même à divisibilité forte, c'est-à-dire que pgcd(UModèle:Ind, UModèle:Ind) soit non seulement divisible par UModèle:Ind mais égal (au signe près), il faut et il suffit que P et Q soient premiers entre euxModèle:,.

Modèle:Démonstration/début Si la suite est à divisibilité forte alors 1 = UModèle:Ind = pgcd(UModèle:Ind, UModèle:Ind) = pgcd(P, PModèle: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, UModèle:Ind 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(UModèle:Ind, Q) = pgcd(PUModèle:Ind, Q) et de l'hypothèse.

On déduit ensuite de cette propriété, jointe à l'identité UModèle:IndUModèle:Ind – UModèle:IndUModèle:Ind = QModèle:ExpUModèle:Ind, que pgcd(UModèle:Ind, UModèle:Ind) divise pgcd(UModèle:Ind, UModèle:Ind) pour 0 < r < n donc (par anthyphérèse) pgcd(UModèle:Ind, UModèle:Ind) divise UModèle:Ind. La divisibilité forte s'ensuit. Modèle:Démonstration/fin

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)=(2\cos \frac{n\pi }{3})=(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 : SModèle:Ind = VModèle:Ind = 4 et SModèle:Ind = SModèle:IndModèle:2 – 2.

Voir aussi

Articles connexes

• LUC (un cryptosystème basé sur les suites de Lucas).
• Nombre pseudo-premier de Fibonacci
• Moyennes d'argent
• Théorème de Zsigmondy