Suite de Padovan

Construction de la suite de Padovan à l'aide de triangles équilatéraux, utilisant la relation P n = P n − 1 + P n − 5 {\displaystyle P_{n}=P_{n-1}+P_{n-5}} . Le nombre dans chaque triangle désigne la longueur de ses côtés.

La suite de Padovan est la suite d'entiers (Pn) définie par récurrence par[1] :

P 0 = P 1 = P 2 = 1  et  ∀ n ∈ N P n + 3 = P n + 1 + P n . {\displaystyle P_{0}=P_{1}=P_{2}=1{\text{ et }}\forall n\in \mathbb {N} \quad P_{n+3}=P_{n+1}+P_{n}.}

C'est une suite récurrente linéaire qui ressemble dans sa forme à la suite de Fibonacci, à une nuance près : la somme des termes de rang n et n + 1 ne donne pas le terme de rang n + 2 mais celui de rang n + 3.

Cette suite d'entiers est strictement croissante à partir du rang 4 ;étendue aux termes d'indice négatifs de sorte que la relation de récurrence ci-dessus soit valable ∀ n ∈ Z {\displaystyle \forall n\in \mathbb {Z} } , elle prend les valeurs :

n -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
P n {\displaystyle P_{n}} 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12

Elle correspond, décalée d'un cran, à la suite A134816 de l'OEIS ( P n = A 134816 ( n + 1 ) {\displaystyle P_{n}=A134816(n+1)} ) et, décalée de cinq crans, à la suite A000931 de l'OEIS ( P n = A 000931 ( n + 5 ) {\displaystyle P_{n}=A000931(n+5)} ).

Elle porte le nom de l'architecte Richard Padovan (en) qui l'a étudiée, et est associée au nombre plastique étudié par l'architecte puis moine Hans van der Laan[2]. Le mathématicien Ian Stewart, dans l'Univers des nombres, évoque et étudie cette suite et lui attribue le nom de suite de Padovan[3] ; il remarque que par une coïncidence heureuse, "Padovan" a la même origine que "Padoue", ville peu éloignée de Pise, dont Fibonacci était originaire.

Le terme général de la suite de Padovan est lié aux trois racines du polynôme X3 – X – 1.

Le quotient de deux termes consécutifs tend vers le nombre plastique.

Formule de type Binet

En fonction des trois racines r1, r2 et r3 de X3 – X – 1 (une réelle et deux complexes conjuguées) on a la formule de type Binet :

P n = ( 1 − r 2 ) ( 1 − r 3 ) ( r 1 − r 2 ) ( r 1 − r 3 ) r 1 n + ( 1 − r 3 ) ( 1 − r 1 ) ( r 2 − r 3 ) ( r 2 − r 1 ) r 2 n + ( 1 − r 1 ) ( 1 − r 2 ) ( r 3 − r 1 ) ( r 3 − r 2 ) r 3 n . {\displaystyle P_{n}={\frac {(1-r_{2})(1-r_{3})}{(r_{1}-r_{2})(r_{1}-r_{3})}}r_{1}^{n}+{\frac {(1-r_{3})(1-r_{1})}{(r_{2}-r_{3})(r_{2}-r_{1})}}r_{2}^{n}+{\frac {(1-r_{1})(1-r_{2})}{(r_{3}-r_{1})(r_{3}-r_{2})}}r_{3}^{n}.}

Les formules de Cardan donnent pour la racine réelle le nombre plastique  :

r 1 = ψ = 1 2 + 69 18 3 + 1 2 − 69 18 3 ≈ 1 , 32472. {\displaystyle r_{1}=\psi ={\sqrt[{3}]{{\frac {1}{2}}+{\frac {\sqrt {69}}{18}}}}+{\sqrt[{3}]{{\frac {1}{2}}-{\frac {\sqrt {69}}{18}}}}\approx 1,32472.}

D'après les relations entre coefficients et racines, on a r 2 + r 3 = − ψ , r 2 r 3 = 1 / ψ {\displaystyle r_{2}+r_{3}=-\psi ,r_{2}r_{3}=1/\psi } , donc r 2 , r 3 {\displaystyle r_{2},r_{3}} , qui sont conjuguées, sont de module 1 ψ < 1 {\displaystyle {\frac {1}{\sqrt {\psi }}}<1} . On obtient :

P n = ψ 5 2 ψ + 3 ψ n + ε n {\displaystyle P_{n}={\frac {\psi ^{5}}{2\psi +3}}\psi ^{n}+\varepsilon _{n}} où ε n → 0 {\displaystyle \varepsilon _{n}\rightarrow 0}

ainsi que P n = ⌊ ψ n + 5 2 ψ + 3 ⌉ {\displaystyle P_{n}=\left\lfloor {\frac {\psi ^{n+5}}{2\psi +3}}\right\rceil } où ⌊ x ⌉ {\displaystyle \left\lfloor x\right\rceil } est l'entier le plus proche de x {\displaystyle x} .

Propriétés

  • Comme pour la suite de Fibonacci, la suite de Padovan s'obtient par puissance n {\displaystyle n} -ième de la matrice compagnon du polynôme caractéristique :
( 0 1 0 0 0 1 1 1 0 ) n ( 1 1 1 ) = ( P n P n + 1 P n + 2 ) {\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}1\\1\\1\end{pmatrix}}={\begin{pmatrix}P_{n}\\P_{n+1}\\P_{n+2}\end{pmatrix}}}
  • La fonction génératrice est donnée par :
    ∑ n = 0 ∞ P n x n = 1 + x 1 − x 2 − x 3 {\displaystyle \sum _{n=0}^{\infty }P_{n}\,x^{n}={\frac {1+x}{1-x^{2}-x^{3}}}}
  • Le nombre de décompositions ordonnées (compositions) de n {\displaystyle n} comme somme de 2 et de 3 est égale à P n − 2 {\displaystyle P_{n-2}} , par exemple, pour n = 8 {\displaystyle n=8} on a 8 = 2 + 3 + 3 = 3 + 2 + 3 = 3 + 3 + 2 = 2 + 2 + 2 + 2.
  • On en déduit l'expression à l'aide de coefficients binomiaux  :
    pour n ⩾ 2 {\displaystyle n\geqslant 2} , P n − 2 = ∑ 2 i + 3 j = n ( i i + j ) = ∑ k = ⌊ n / 3 ⌋ ⌊ n / 2 ⌋ ( k n − 2 k ) {\displaystyle P_{n-2}=\sum _{2i+3j=n}{\binom {i}{i+j}}=\sum _{k=\lfloor n/3\rfloor }^{\lfloor n/2\rfloor }{\binom {k}{n-2k}}}
  • Les nombres de Padovan premiers sont 2, 3, 5, 7, 37, 151, etc. (suite A100891 de l'OEIS).

Variantes

On trouve parfois des initialisations différentes comme dans les suites OEIS A000931, OEIS A078027, OEIS A096231, OEIS A124745, OEIS A133034, OEIS A164001, OEIS A182097, OEIS A228361, OEIS A020720 et OEIS A001608 de l'OEIS.

Cette dernière est la suite de Perrin : 3, 0, 2, 3, 2, 5, etc.

Notes et références

  1. ↑ (en) Eric W. Weisstein, « Padovan sequence », sur MathWorld.
  2. ↑ (en) Richard Padovan presents the plastic number, résumé du Nexus Network Journal
  3. ↑ Ian Stewart, L'univers des nombres, Belin, , p. 19-20
  • icône décorative Arithmétique et théorie des nombres