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[1].

Définition par récurrence

Soient P et Q deux entiers non nuls tels que

Δ = P 2 − 4 Q ≠ 0 {\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

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 )  pour  n ⩾ 2 {\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

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 )  pour  n ⩾ 2. {\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.}

Terme général

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

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

a = P + δ 2 e t b = P − δ 2 . {\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] :

U n ( P , Q ) = a n − b n a − b = a n − b n δ e t V n ( P , Q ) = a n + b n , {\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

a n = V n + U n δ 2 e t b n = V n − U n δ 2 . {\displaystyle 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[3], qui généralisent celles entre les nombres de Fibonacci et les nombres de Lucas. Par exemple[b] :

( ∗ ) U n U m + r − U r U m + n = Q r U n − r U m {\displaystyle (*)\quad U_{n}U_{m+r}-U_{r}U_{m+n}=Q^{r}U_{n-r}U_{m}} [c]
( ∗ ∗ ) U m + n = {\displaystyle (**)\quad U_{m+n}=} [d],[4] U n U m + 1 − Q U n − 1 U m = U n V m + U m V n 2 {\displaystyle 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 = Δ U m U n + V m V n 2 , {\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

U n + 1 = P U n + V n 2 = V n + Q U n − 1 , V n + 1 = Δ U n + P V n 2 = Δ U n + Q V n − 1 {\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

U 2 n = U n V n , V 2 n = V n 2 − 2 Q n . {\displaystyle U_{2n}=U_{n}V_{n},\qquad V_{2n}=V_{n}^{2}-2Q^{n}.}

Divisibilité

De la deuxième identité ci-dessus, (**) Um+n = UnUm+1 – QUn–1Um, on déduit immédiatement (par récurrence sur k) que Unk est toujours un multiple de Un : on dit que la suite U(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 {\displaystyle k>0} et, pour alléger l'écriture, U n ≠ 0 {\displaystyle U_{n}\neq 0} (dans le cas U n = 0 {\displaystyle U_{n}=0} , il suffit d'écrire les égalités correspondantes sans division par U n {\displaystyle U_{n}} ).

U n k U n = a n k − b n k a n − b n = ∑ j = 0 k − 1 a n ( k − 1 − j ) b n j = ( 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 2 n + b n ( k − 3 ) a 2 n ) + … = ( a n ( k − 1 ) + b n ( k − 1 ) ) + Q n ( a n ( k − 3 ) + b n ( k − 3 ) ) + Q 2 n ( a n ( k − 5 ) + b n ( k − 5 ) ) + … = V n ( k − 1 ) + Q n V n ( k − 3 ) + Q 2 n V n ( k − 5 ) + … ∈ Z . {\displaystyle {\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(Ui, Uj) soit non seulement divisible par Upgcd(i, j) mais égal (au signe près), il faut et il suffit que P et Q soient premiers entre eux[b],[5].

Démonstration[e]

Si la suite est à divisibilité forte alors 1 = U1 = pgcd(U2, U3) = pgcd(P, P2 – Q) = pgcd(P, Q).

Réciproquement, supposons que pgcd(P, Q) = 1 et montrons d'abord par récurrence que pour tout n ≥ 1, Un 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(Un+1, Q) = pgcd(PUn, Q) et de l'hypothèse.

On déduit ensuite de cette propriété, jointe à l'identité UnUr+1 – UrUn+1 = QrUn–r[d], que pgcd(Un, Ur) divise pgcd(Un–r, Ur) pour 0 < r < n donc (par anthyphérèse) pgcd(Ui, Uj) divise Upgcd(i, j). La divisibilité forte s'ensuit.

Cas particuliers

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

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

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

U ( 1 , − 2 ) {\displaystyle U(1,-2)} est la suite de Jacobstahl et V ( 1 , − 2 ) {\displaystyle V(1,-2)} la suite de Jacobsthal-Lucas.
U ( 1 , 1 ) = ( 2 sin ⁡ n π 3 3 ) = ( 0 , 1 , 1 , 0 , − 1 , − 1 , 0 , . . . ) {\displaystyle 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 ⁡ n π 3 ) = ( 2 , 1 , − 1 , − 2 , − 1 , 1 , 2 , . . . ) {\displaystyle V(1,1)=\left(2\cos {\frac {n\pi }{3}}\right)=(2,1,-1,-2,-1,1,2,...)} .
S k := V 2 k ( 2 , − 1 ) {\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 : S1 = V2 = 4 et Sk+1 = Sk2 – 2.

Notes et références

(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

  1. ↑ Dans le cas Δ = 0, on a U n ( P , Q ) = n a n − 1 {\displaystyle U_{n}(P,Q)=na^{n-1}} et V n ( P , Q ) = 2 a n {\displaystyle V_{n}(P,Q)=2a^{n}} , avec a = b = P / 2 {\displaystyle a=b=P/2} .
  2. ↑ a et b Y compris dans les cas dégénérés.
  3. ↑ 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 l'expression de Un en fonction de a et b.
  4. ↑ a et b Cette équation se déduit de (*).
  5. ↑ L'anneau dans lequel la suite prend ses valeurs (ici : l'anneau des entiers) peut être remplacé par n'importe quel anneau intègre à PGCD.

Références

  1. ↑ Édouard Lucas, « Théorie des fonctions numériques simplement périodiques », Amer. J. Math., vol. 1, no 2,‎ , p. 184-196, 197-240, 289-321 (lire en ligne).
  2. ↑ C'est le choix adopté par Ribenboim 2006, p. 2. (en) D. H. Lehmer, « An extended theory of Lucas' functions », Ann. Math., 2e série, vol. 31,‎ , p. 419-448 (JSTOR 1968235), 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.
  3. ↑ « A look at the issues of The 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.
  4. ↑ (en) Peter Bala, « Divisibility sequences from strong divisibility sequences », sur OEIS, , p. 9, Proposition A.3.
  5. ↑ Ribenboim 2006, p. 9 ; Lucas 1878, p. 206 ; Bala 2014, Appendix (p. 8-10).

Voir aussi

Articles connexes

Bibliographie

(en) Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer, (lire en ligne), chap. 1

Lien externe

(en) Eric W. Weisstein, « Lucas Sequence », sur MathWorld

  • icône décorative Portail des mathématiques