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<ref>Modèle:Article.</ref>.

Définition par récurrence

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

<math>\Delta=P^2 - 4Q\ne0</math>

(pour éviter les cas dégénérés)<ref>C'est le choix adopté par Modèle:Harvsp. Modèle:Article, l'étend au cas où P est la racine carrée d'un entier premier avec Q. Lucas prenait P et Q entiers premiers entre eux.</ref>.

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

<math>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\geqslant2</math>

et

<math>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\geqslant2.</math>

Terme général

Notons <math>\delta</math> 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

<math>a=\frac{P+\delta}2\quad{\rm et}\quad b=\frac{P-\delta}2.

</math> 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<ref group=alpha>Dans le cas Modèle:Math, on a <math>U_n(P,Q)=na^{n-1}</math> et <math>V_n(P,Q)=2a^n</math>, avec <math>a=b=P/2</math>.</ref> :

<math>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,</math>

dont on peut tirer les relations

<math>a^n = \frac{V_n + U_n \delta}2\quad{\rm et}\quad b^n = \frac{V_n - U_n \delta}2.</math>

Autres relations

Les nombres dans les suites de Lucas satisfont à de nombreuses relations<ref>Modèle:Citation étrangère Modèle:Harvsp.</ref>, qui généralisent celles entre les nombres de Fibonacci et les nombres de Lucas. Par exemple<ref group=alpha name=degenere/> : Modèle:Ancre

<math>(*)\quad U_nU_{m+r}-U_rU_{m+n}=Q^rU_{n-r}U_m</math><ref group=alpha>Cette équation est un cas particulier des identités remarquables vérifiées par les suites récurrentes linéaires d'ordre 2, mais peut aussi se déduire directement de [[#Terme général|l'expression de Modèle:Mvar en fonction de Modèle:Mvar et Modèle:Mvar]].</ref>

<math>(**)\quad U_{m+n}=</math><ref group=alpha name=Corollaire>Cette équation se déduit de [[#equation|Modèle:Math]].</ref><ref>Modèle:Lien web, Proposition A.3.</ref> <math>U_nU_{m+1}-QU_{n-1}U_m={U_nV_m+U_mV_n\over2}</math> et

<math>V_{m+n}=V_mV_n-Q^mV_{n-m}={\Delta U_mU_n+V_mV_n\over2},</math>

en particulier

<math>U_{n+1}={PU_n+V_n\over2}=V_n+QU_{n-1},\qquad V_{n+1}={\Delta U_n+PV_n\over2}=\Delta U_n+QV_{n-1}</math>

et

<math>U_{2n} = U_n V_n,\qquad V_{2n} = V_n^2 - 2Q^n.</math>

Divisibilité

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. Modèle:Démonstration{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^nV_{n(k-3)}+Q^{2n}V_{n(k-5)}+\ldots\in\Z. \end{align}</math> }}

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<ref group=alpha name=degenere>Y compris dans les cas dégénérés.</ref><ref>Modèle:Harvsp ; Modèle:Harvsp ; Modèle:Harvsp.</ref>.

Modèle:Démonstration/début Si la suite est à divisibilité forte alors 1 = U₁ = pgcd(U₂, U₃) = pgcd(P, P² – 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<ref group=alpha name=Corollaire/>, 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. Modèle:Démonstration/fin

Cas particuliers

<math>U(1,-1)</math> est la suite de Fibonacci et <math>V(1,-1)</math> la suite de Fibonacci-Lucas.

<math>U(2,-1)</math> est la suite de Pell et <math>V(2,-1)</math> la suite de Pell-Lucas.

Plus généralement, <math>U_n(P,-1)</math> et <math>V_n(P,-1)</math> sont les valeurs en P du n-ième polynôme de Fibonacci et du n-ième polynôme de Lucas.

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

<math>U(1,-2)</math> est la suite de Jacobstahl et <math>V(1,-2)</math> la suite de Jacobsthal-Lucas.

<math>U(1,1)=\left ( \frac{2\sin\frac{n\pi}{3}}{\sqrt3} \right )=(0,1,1,0,-1,-1,0,...)</math>, <math>V(1,1)=\left ( 2\cos\frac{n\pi}{3} \right )=(2,1,-1,-2,-1,1,2,...)</math>.

<math>S_k:=V_{2^k}(\sqrt2,-1)</math> (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.

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