Suite de Tribonacci

La suite de Tribonacci est définie par :

• ${\displaystyle T_{0}=0}$, ${\displaystyle T_{1}=1}$, ${\displaystyle T_{2}=1}$ ;
• pour tout entier naturel n, ${\displaystyle T_{n+3}=T_{n+2}+T_{n+1}+T_{n}}$.

Les dix premiers termes sont donc : 0, 1, 1, 2, 4, 7, 13, 24, 44, 81 (suite A000073 de l'OEIS).

L'étude des suites récurrentes linéaires permet de dire que cette suite est combinaison linéaire des trois suites ${\displaystyle (r_{1}^{n})}$, ${\displaystyle (r_{2}^{n})}$, ${\displaystyle (r_{3}^{n})}$ où les ${\displaystyle r_{i}}$ sont les trois racines du polynôme ${\displaystyle X^{3}-X^{2}-X-1}$.

• La racine réelle (environ égale à 1,839 [1]) est appelée constante de Tribonacci et correspond à la limite du quotient de deux termes consécutifs. Les formules de Cardan en donnent une valeur exacte [1] :

  ${\displaystyle {\frac {{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}+1}{3}}}$.

• Les deux racines complexes sont conjuguées l'une de l'autre et de module inférieur à 1. Elles sont parfois appelées nombres de Tribonacci ^{[réf. souhaitée]}.

Le terme général de la suite est alors :

${\displaystyle T_{n}=a_{1}r_{1}^{n}+a_{2}r_{2}^{n}+a_{3}r_{3}^{n}}$ où les ${\displaystyle a_{i}}$ sont donnés par les formules suivantes :

${\displaystyle a_{1}={\frac {r_{1}}{(r_{1}-r_{2})(r_{1}-r_{3})}}}$

${\displaystyle a_{2}={\frac {r_{2}}{(r_{2}-r_{3})(r_{2}-r_{1})}}}$

${\displaystyle a_{3}={\frac {r_{3}}{(r_{3}-r_{1})(r_{3}-r_{2})}}}$

On peut aussi travailler sur la série génératrice de cette suite, c’est-à-dire la série formelle :

• ${\displaystyle F=\sum T_{n}X^{n}}$.

La série génératrice de la suite ${\displaystyle T_{n-1}}$ est alors XF, celle de ${\displaystyle T_{n-2}}$ est ${\displaystyle X^{2}F}$ et celle de ${\displaystyle T_{n-3}}$ est ${\displaystyle X^{3}F}$ ; la relation de récurrence ${\displaystyle T_{n}=T_{n-1}+T_{n-2}+T_{n-3}}$, valable pour tout n supérieur ou égal à 3, assure que

${\displaystyle F=XF+X^{2}F+X^{3}F+X+X^{2}-X^{2}}$.

Les termes en complément correspondent aux 3 premiers termes des suites. Il suffit alors de résoudre cette équation. La fonction génératrice de la suite est donc :

${\displaystyle F={\frac {X}{1-X-X^{2}-X^{3}}}=X+X^{2}+2X^{3}+4X^{3}+7X^{4}+\dots }$

Verner Emil Hoggatt Jr. (en) a prouvé en 1980[2]^{[réf. à confirmer]} qu'il existe une partition de ℕ en deux ensembles dont la somme ne contient aucun élément de la suite de Tribonacci.

C'est la suite de mots définie par :

M(1) = a

et par la substitution de Tribonacci suivante :

a donne ab, b donne ac et c donne a

Nous obtenons alors la suite de mots suivants : a, ab, ab|ac, abac|ab|a, abacaba|abac|ab, abacabaabacab|abacaba|abac... On s'aperçoit ainsi que chaque mot est obtenu comme la concaténation des 3 mots précédents. Il n'est donc pas surprenant que la longueur de ces mots soit une suite d'entiers de Tribonacci. Le mot infini obtenu à la limite est le mot infini de Tribonacci. C'est un mot purement morphique.

La suite de mots intervient dans la construction de la fractale de Rauzy.

On démontre[3] que T_{n + 1} est le nombre de façons de découper un segment de longueur n en segments de longueur 1, 2 ou 3.

De manière plus générale[3], le terme d'indice n + 1 d'une suite de k-bonacci correspond au nombre de façons de découper un segment de longueur n en segments de longueur comprise entre 1 et k.