Suite de Padovan

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

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 $\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}$	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}=A134816(n+1)$ ) et, décalée de cinq crans, à la suite A000931 de l'OEIS ( $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 $X 3 - X - 1$ .

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

Formule de type Binet[modifier | modifier le code]

En fonction des trois racines $r 1$ , $r 2$ et $r 3$ de $X 3 - X - 1$ (une réelle et deux complexes conjuguées) on a la formule de type Binet :

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}=\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}=-\psi ,r_{2}r_{3}=1/\psi$ , donc $r_{2},r_{3}$ , qui sont conjuguées, sont de module ${\frac {1}{\sqrt {\psi }}}<1$ . On obtient :

P_{n}={\frac {\psi ^{5}}{2\psi +3}}\psi ^{n}+\varepsilon _{n}

où

\varepsilon _{n}\rightarrow 0

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

Propriétés[modifier | modifier le code]

Comme pour la suite de Fibonacci, la suite de Padovan s'obtient par puissance $n$ -ième de la matrice compagnon du polynôme caractéristique :

{\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 :
$\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$ comme somme de 2 et de 3 est égale à $P_{n-2}$ , par exemple, pour $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\geqslant 2$ , $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).