suite de Padovan

Écrivez trois fois 1. Pour obtenir un nouveau nombre, sautez le terme qui le précède immédiatement et additionnez les deux termes antérieurs à celui-ci. Après 1, 1, 1 viennent ainsi 2, 2, 3, 4, 5 puis 7. Cette liste est la suite de Padovan. Sa croissance n'est pas régulière à chaque pas, mais le rapport entre deux termes consécutifs se rapproche peu à peu d'un nombre voisin de 1,32, appelé nombre plastique.

La suite de Padovan est une suite d'entiers. Le symbole u_n désigne son terme d'indice n, où n est un entier positif ou nul. Ses trois valeurs initiales sont u₀ = u₁ = u₂ = 1. Pour chaque entier n positif ou nul, la règle est $u_{n+3}=u_{n+1}+u_{n}u\_\{n+3\}=u\_\{n+1\}+u\_n$. Chaque nouveau terme est donc la somme de u_n+1 et u_n, tandis que u_n+2, le terme immédiatement précédent, n'intervient pas. Cette règle et les trois valeurs initiales déterminent toute la suite.

Le quotient du terme suivant par le terme courant, écrit $\frac{u_{n+1}}{u_n}\backslash frac\{u\_\{n+1\}\}\{u\_n\}$, tend vers l'unique racine réelle positive de $x^3=x+1x^3=x+1$. Cette racine est un nombre algébrique irrationnel d'environ 1,32, appelé nombre plastique et parfois nombre d'argent. La suite porte le nom de l'architecte britannique Richard Padovan (1935–2007). Elle admet aussi une construction géométrique avec des triangles équilatéraux imbriqués.

Quatre éléments organisent la suite. Les indices 0, 1, 2, 3… ordonnent les positions. Les trois termes initiaux, tous égaux à 1, amorcent le calcul. La relation de récurrence indique ensuite quels termes additionner. Enfin, les termes obtenus deviennent à leur tour les données des calculs suivants.

La dépendance saute le terme immédiatement précédent : pour trouver u₈, on omet u₇ et on additionne les termes consécutifs u₆ et u₅. Les valeurs initiales et cette règle suffisent à construire chaque entier de la liste. Les rapports entre termes consécutifs forment une information dérivée : ils ne définissent pas la suite, mais révèlent sa tendance vers le nombre plastique.

Partons des seules données initiales : u₀ = 1, u₁ = 1 et u₂ = 1. L'objectif est de construire les termes jusqu'à l'indice 8 en appliquant toujours la même règle.

1. Les deux premiers calculs donnent $u_3=u_1+u_0=2u\_3=u\_1+u\_0=2$ puis $u_4=u_2+u_1=2u\_4=u\_2+u\_1=2$.

2. Les termes suivants sont $u_5=u_3+u_2=3u\_5=u\_3+u\_2=3$ et $u_6=u_4+u_3=4u\_6=u\_4+u\_3=4$.

3. On poursuit avec $u_7=u_5+u_4=5u\_7=u\_5+u\_4=5$, puis $u_8=u_6+u_5=7u\_8=u\_6+u\_5=7$.

La liste obtenue est donc 1, 1, 1, 2, 2, 3, 4, 5, 7. Le schéma associé met en évidence le dernier calcul, où les valeurs 4 et 3 produisent 7.

Un contrôle refaisable consiste à calculer le terme suivant : $u_9=u_7+u_6=5+4=9u\_9=u\_7+u\_6=5+4=9$. On retrouve bien le dixième terme annoncé dans la suite.

Pour prolonger la liste exactement, on garde les termes déjà calculés et on applique la récurrence indice après indice. Cette voie convient quand les valeurs entières importent davantage que leur tendance.

Pour observer la croissance à long terme, on divise chaque terme non nul par le précédent. Les quotients ne valent pas tous 1,32 : ils s'en rapprochent. On préfère donc les rapports à la simple liste lorsqu'on cherche le nombre plastique.

Pour donner une lecture géométrique à la suite, on peut suivre la construction par triangles équilatéraux imbriqués mentionnée dans sa définition. La récurrence reste le meilleur contrôle des nombres portés par cette construction.

Suite de Fibonacci. Les deux suites sont récurrentes, mais leur test de calcul diffère. Fibonacci additionne les deux termes consécutifs précédents ; Padovan saute le terme immédiatement précédent et additionne les deux termes antérieurs à celui-ci. Avec trois 1 au départ, Padovan donne 1, 1, 1, 2, 2, tandis que la règle de Fibonacci ne reproduit pas ce début.

Nombre d'or. Le nombre plastique joue ici un rôle analogue, mais il est lié à l'équation cubique x³ = x + 1 et vaut environ 1,32. Le nom de « nombre d'argent » parfois employé pour lui ne le transforme donc pas en nombre d'or.

Les valeurs initiales sont indispensables. La relation seule ne sélectionne pas la suite présentée ici. Si l'un des trois premiers termes change, le symptôme est immédiat : la liste calculée diverge de 1, 1, 1, 2, 2… Il faut donc fixer u₀ = u₁ = u₂ = 1 avant de commencer.

1,32 est une approximation. Les rapports consécutifs 1/1, 2/1 ou 3/2 ne sont ni constants ni tous égaux à cette valeur. Il faut calculer des termes de plus en plus lointains et parler d'une limite, pas remplacer chaque quotient par 1,32.

Le décalage des indices peut tromper. Avec la convention qui commence à u₀, le terme 7 porte l'indice 8. Si une liste est numérotée à partir de 1, ses valeurs restent identiques mais leurs indices changent ; il faut annoncer la convention avant de comparer deux écritures.

La suite de Fibonacci permet de comparer deux règles de récurrence proches en apparence et de repérer exactement les termes additionnés.

Le nombre d'or éclaire l'analogie annoncée avec le nombre plastique, tout en aidant à ne pas confondre ces deux limites.

L'article Un orfèvre du raisonnement par récurrence ouvre sur une autre facette de la récurrence, cette fois comme mode de raisonnement.