Suite de Tribonacci

La suite de Tribonacci étudiée ici 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 décalée d'un cran).

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 r_{1}=\alpha _{3}={\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.

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})}}}$

mais on a aussi, uniquement en fonction de ${\displaystyle \alpha _{3}}$ [2] :

${\displaystyle T_{n}=\left\lfloor {\frac {\alpha _{3}^{n-1}(\alpha _{3}-1)}{4\alpha _{3}-6}}\right\rceil ,}$ où et ${\displaystyle \left\lfloor .\right\rceil }$ désigne la fonction "entier le plus proche".

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[3] qu'il existe une partition de ℕ en deux ensembles dont la somme ne contient aucun élément de la suite de Tribonacci.

T_n+1 est égal au nombre de suites finies d'entiers égaux à 1, 2 ou 3 dont la somme est égale à n , c'est-à-dire le nombre de compositions de n formées à partir de ces entiers ; par exemple ${\displaystyle T_{4}=4}$ car 3 s'écrit ${\displaystyle 1+1+1,1+2,2+1,{\text{ou }}3}$ [4] - [5].

De façon imagée, T_n+1 est le nombre de façons de vider un tonneau de n litres à l'aide de bouteilles de un, deux, ou trois litres, ou le nombre de façons de découper un segment de longueur n en segments de longueur 1, 2 ou 3.

Démonstration : les compositions de n se terminant par 1 sont obtenues en ajoutant 1 à la fin d'une composition de ${\displaystyle n-1}$, celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de ${\displaystyle n-2}$, celles se terminant par 3 sont obtenues en ajoutant 3 à la fin d'une composition de ${\displaystyle n-3}$ , donc le nombre ${\displaystyle C_{n}}$ de composition de n vérifie ${\displaystyle C_{n}=C_{n-1}+C_{n-2}+C_{n-3}}$. De plus, ${\displaystyle C_{0}=T_{1}=1}$ (la composition vide), ${\displaystyle C_{1}=T_{2}=1}$ (la composition (1)), ${\displaystyle C_{2}=T_{3}=2}$ (les compositions (1,1) et (2)), ce qui montre la relation.

De manière plus générale[4], le terme d'indice n + 1 d'une suite de k-bonacci (chaque terme est la somme des k précédents, les termes d'indice ${\displaystyle 0,1,2,3,\cdots ,k-1}$ étant égaux à ${\displaystyle \left(0,1,1,2,\cdots ,2^{k-3}\right)}$ correspond au nombre de compositions de n formées à partir des entier de 1 à k.

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.