Movatterモバイル変換

Suite de Lucas

Un article de Wikipédia, l'encyclopédie libre.

Enmathématiques, lessuites de LucasU(P,Q) etV(P,Q) associées à deuxentiersP etQ sont deuxsuites récurrentes linéaires d'ordre2 à valeurs entières qui généralisent respectivement lasuite de Fibonacci etcelle de Fibonacci-Lucas, correspondant aux valeursP = 1 etQ = –1.

Elles doivent leur nom aumathématicien français Édouard Lucas^[1].

Définition par récurrence

[modifier |modifier le code]

SoientP etQ deux entiers non nuls tels que

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

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

Les suites de LucasU(P,Q) etV(P,Q) sontdé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

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

[modifier |modifier le code]

Notons $\delta$ l'une des deuxracines carrées deΔ (éventuellement dansℂ).

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

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

AlorsU(P,Q) etV(P,Q) peuvent aussi être définies en fonction dea etb par l'analogue suivant de laformule de Binet^[a] :

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

[modifier |modifier le code]

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] :

(*)\quad U_{n}U_{m+r}-U_{r}U_{m+n}=Q^{r}U_{n-r}U_{m}

^[c]

(**)\quad U_{m+n}=

^[d]^,^[4]

U_{n}U_{m+1}-QU_{n-1}U_{m}={U_{n}V_{m}+U_{m}V_{n} \over 2}

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}

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

Divisibilité

[modifier |modifier le code]

De la deuxièmeidentité ci-dessus, (**)U_m+n = U_nU_m+1 –QU_n–1U_m, on déduit immédiatement (par récurrence surk) queU_nk est toujours un multiple deU_n : on dit que la suiteU(P,Q) est àdivisibilité faible.

Variante par calcul du quotient

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 quepgcd(U_i,U_j) soit non seulement divisible parU_pgcd(i,j) mais égal (au signe près), il faut et il suffit queP etQ soientpremiers entre eux^[b]^,^[5].

Démonstration^[e]

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 toutn ≥ 1,U_n estpremier avecQ.

L'initialisation est immédiate, et l'hérédité se déduit (grâce aulemme 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^[d], que pgcd(U_n,U_r) divise pgcd(U_n–r,U_r) pour 0 <r <n donc (paranthyphérèse) pgcd(U_i,U_j) diviseU_pgcd(i,j). La divisibilité forte s'ensuit.

Cas particuliers

[modifier |modifier le code]

U(1,-1)

est lasuite de Fibonacci et

V(1,-1)

lasuite de Fibonacci-Lucas.

U(2,-1)

est lasuite de Pell et

V(2,-1)

lasuite de Pell-Lucas.

Plus généralement, $U_{n}(P,-1)$ et $V_{n}(P,-1)$ sont les valeurs enP dun-ièmepolynôme de Fibonacci et dun-ièmepolynô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 desnombres de Mersenne et plus généralement, $U(b+1,b)$ qui est la suite desrépunits en baseb.

U(1,-2)

est lasuite 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 letest de primalité de Lucas-Lehmer pour les nombres de Mersenne :S₁ =V₂ = 4 etS_k+1 =S_k² – 2.

Notes et références

[modifier |modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé« Lucas sequence »(voir la liste des auteurs).

Notes

[modifier |modifier le code]

↑Dans le casΔ = 0, on a $U_{n}(P,Q)=na^{n-1}$ et $V_{n}(P,Q)=2a^{n}$ , avec $a=b=P/2$ .
↑^{a etb}Y compris dans les cas dégénérés.
↑Cette équation est un cas particulier desidentités remarquables vérifiées par les suites récurrentes linéaires d'ordre 2, mais peut aussi se déduire directement del'expression deU_n en fonction dea etb.
↑^{a etb}Cette équation se déduit de(*).
↑L'anneau dans lequel la suite prend ses valeurs (ici : l'anneau desentiers) peut être remplacé par n'importe quelanneau intègre à PGCD.

Références

[modifier |modifier le code]

↑Édouard Lucas, « Théorie des fonctions numériques simplement périodiques »,Amer. J. Math.,vol. 1,n^o 2,‎1878,p. 184-196, 197-240, 289-321(lire en ligne).
↑C'est le choix adopté parRibenboim 2006,p. 2.(en)D. H. Lehmer, « An extended theory of Lucas' functions »,Ann. Math.,2^e série,vol. 31,‎1930,p. 419-448(JSTOR 1968235), l'étend au cas oùP est laracine carrée d'un entierpremier avecQ. Lucas prenaitP etQ entiers premiers entre eux.
↑« A look at the issues ofThe Fibonacci Quarterly will leave the impression that there is no bound to the imagination of mathematicians whose endeavor it is to produce newer forms of these identities and properties. […] I shall select a small number of formulas that I consider most useful. Their proofs are almost always simple exercises, either by applying Binet's formulas or by induction. »Ribenboim 2006,p. 2.
↑(en) Peter Bala, « Divisibility sequences from strong divisibility sequences », surOEIS,2014,p. 9, Proposition A.3.
↑Ribenboim 2006,p. 9 ;Lucas 1878,p. 206 ;Bala 2014, Appendix (p. 8-10).