Suite de Tribonacci

Une suite de Tribonacci est une suite d'entiers dont la relation de récurrence est inspirée de celle de la suite de Fibonacci : chaque terme est la somme des trois termes qui le précèdent (dans une suite de Fibonacci, chaque terme est la somme des deux termes qui le précèdent).

Le terme de Tribonacci est un néologisme formé de tri (récurrence à trois termes) et de bonacci (en allusion au mathématicien Fibonacci). Il a été suggéré par Feinberg en 1963[1]. Il existe de même des suites de Tetranacci où chaque terme est la somme des 4 termes qui le précèdent et même des suites de k-bonacci où chaque terme est la somme des k termes qui le précèdent.

On définit aussi une suite de mots de Tribonacci, construite à partir de trois lettres à l'aide de la substitution de Tribonacci : a donne ab, b donne ac et c donne a.

Étude mathématique

  • La suite de Tribonacci étudiée ici est définie par :
    • T 0 = 0 {\displaystyle T_{0}=0} , T 1 = 1 {\displaystyle T_{1}=1} , T 2 = 1 {\displaystyle T_{2}=1}  ;
    • pour tout entier naturel n, T n + 3 = T n + 2 + T n + 1 + T 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 : T n = A 000073 ( n + 1 ) {\displaystyle T_{n}=A000073(n+1)} ).
  • La relation de récurrence peut s'écrire aussi : T n = T n − 1 + T n − 2 + T n − 3 = 2 T n − 1 − T n − 4 {\displaystyle T_{n}=T_{n-1}+T_{n-2}+T_{n-3}=2T_{n-1}-T_{n-4}} pour n ⩾ 4 {\displaystyle n\geqslant 4} .
  • Comme [ 0 1 0 0 0 1 1 1 1 ] [ T n − 1 T n T n + 1 ] = [ T n T n + 1 T n + 2 ] {\displaystyle {\begin{bmatrix}0&1&0\\0&0&1\\1&1&1\end{bmatrix}}{\begin{bmatrix}T_{n-1}\\T_{n}\\T_{n+1}\end{bmatrix}}={\begin{bmatrix}T_{n}\\T_{n+1}\\T_{n+2}\end{bmatrix}}} , on a :
[ T n T n + 1 T n + 2 ] = [ 0 1 0 0 0 1 1 1 1 ] n [ 0 1 1 ] {\displaystyle {\begin{bmatrix}T_{n}\\T_{n+1}\\T_{n+2}\end{bmatrix}}={\begin{bmatrix}0&1&0\\0&0&1\\1&1&1\end{bmatrix}}^{n}{\begin{bmatrix}0\\1\\1\end{bmatrix}}}
F = X + X 2 + 2 X 3 + 4 X 3 + 7 X 4 + ⋯ = ∑ n ⩾ 0 T n X n = X 1 − X − X 2 − X 3 {\displaystyle F=X+X^{2}+2X^{3}+4X^{3}+7X^{4}+\dots =\sum _{n\geqslant 0}T_{n}X^{n}={\frac {X}{1-X-X^{2}-X^{3}}}} .
Démonstration

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

F = X F + X 2 F + X 3 F + X + X 2 − X 2 {\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 :

F = X 1 − X − X 2 − X 3 {\displaystyle F={\frac {X}{1-X-X^{2}-X^{3}}}} .
  • Verner Emil Hoggatt Jr. (en) a prouvé en 1980[2] qu'il existe une partition de ℕ en deux ensembles dont la somme ne contient aucun élément de la suite de Tribonacci.

Formule de type Binet

L'étude des suites récurrentes linéaires permet de dire que cette suite est combinaison linéaire des trois suites ( τ n ) {\displaystyle (\tau ^{n})} , ( r n ) {\displaystyle (r^{n})} , ( r ¯ n ) {\displaystyle ({\overline {r}}^{n})} où τ , r , r ¯ {\displaystyle \tau ,r,{\overline {r}}} sont les trois racines du polynôme X 3 − X 2 − X − 1 {\displaystyle X^{3}-X^{2}-X-1} . La racine réelle (environ égale à 1,839), notée τ {\displaystyle \tau } par analogie avec la notation φ {\displaystyle \varphi } du nombre d'or ou constante de Fibonacci, est appelée constante de Tribonacci. Elle est égale à la limite du quotient (suivant sur précédent) de deux termes consécutifs. Les formules de Cardan en donnent une valeur exacte[3]:

τ = 19 + 3 33 3 + 19 − 3 33 3 + 1 3 {\displaystyle \tau ={\frac {{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}+1}{3}}} .

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

T n = a 1 τ n + a 2 r n + a 3 r ¯ n {\displaystyle T_{n}=a_{1}\tau ^{n}+a_{2}r^{n}+a_{3}{\overline {r}}^{n}} où les a i {\displaystyle a_{i}} sont donnés par les formules suivantes [1] :
a 1 = τ | τ − r | 2 {\displaystyle a_{1}={\frac {\tau }{|\tau -r|^{2}}}}
a 2 = r ( r − r ¯ ) ( r − τ ) {\displaystyle a_{2}={\frac {r}{(r-{\overline {r}})(r-\tau )}}}
a 3 = a 2 ¯ {\displaystyle a_{3}={\overline {a_{2}}}}

D'après les relations entre coefficients et racines, on a r + r ¯ = 1 − τ , r r ¯ = 1 / τ {\displaystyle r+{\overline {r}}=1-\tau ,r{\overline {r}}=1/\tau } , donc r , r ¯ {\displaystyle r,{\overline {r}}} , sont de module 1 τ < 1 {\displaystyle {\frac {1}{\sqrt {\tau }}}<1} . On obtient :

T n = τ n τ ( 5 − τ 2 ) + ε n {\displaystyle T_{n}={\frac {\tau ^{n}}{\tau (5-\tau ^{2})}}+\varepsilon _{n}} où ε n → 0 {\displaystyle \varepsilon _{n}\rightarrow 0} ,

et aussi, uniquement en fonction de τ {\displaystyle \tau } [4],[5] :

T n = ⌊ τ n r 1 ( 5 − τ 2 ) ⌉ , {\displaystyle T_{n}=\left\lfloor {\frac {\tau ^{n}}{r_{1}(5-\tau ^{2})}}\right\rceil ,}

où ⌊ . ⌉ {\displaystyle \left\lfloor .\right\rceil } désigne la fonction « entier le plus proche ».

Propriétés de la constante de Tribonacci

On a  :

τ = 1 + 19 + 3 33 3 + 19 − 3 33 3 3 = 1 + 4 cosh ⁡ ( 1 3 cosh − 1 ⁡ ( 2 + 3 8 ) ) 3 ≈ 1,839 286 755 214 161 {\displaystyle \tau ={\frac {1+{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}}{3}}={\frac {1+4\cosh \left({\tfrac {1}{3}}\cosh ^{-1}\left(2+{\tfrac {3}{8}}\right)\right)}{3}}\approx 1{,}839\,286\,755\,214\,161} , décimales données par la suite A058265 de l'OEIS.

Cette constante vérifie par définition :

τ 3 = τ 2 + τ + 1 {\displaystyle \tau ^{3}=\tau ^{2}+\tau +1} , soit τ = 1 + 1 τ + 1 τ 2 {\displaystyle \tau =1+{\frac {1}{\tau }}+{\frac {1}{\tau ^{2}}}} et 1 τ + 1 τ 2 + 1 τ 3 = 1 {\displaystyle {\frac {1}{\tau }}+{\frac {1}{\tau ^{2}}}+{\frac {1}{\tau ^{3}}}=1}

donc aussi :

τ 4 = 2 τ 3 − 1 {\displaystyle \tau ^{4}=2\tau ^{3}-1} soit τ + 1 τ 3 = 2 {\displaystyle \tau +{\frac {1}{\tau ^{3}}}=2}

Son inverse, solution positive de x3 + x2 + x = 1 a pour décimales la suite A192918 de l'OEIS.

Elle intervient dans les coordonnées des sommets du cube adouci.

Construction géométrique de la constante de Tribonacci.

Construction géométrique

La constante de Tribonacci, algébrique de degré 3, n'est pas constructible à la règle et au compas, mais on peut la construire à la règle graduée et au compas.

Dans la figure ci-contre, posant α = B A C ^ = B D C ^ {\displaystyle \alpha ={\widehat {BAC}}={\widehat {BDC}}} , on a B D = tan ⁡ α 2 = cos ⁡ α {\displaystyle BD=\tan {\frac {\alpha }{2}}=\cos \alpha } , donc, posant t = tan ⁡ α 2 {\displaystyle t=\tan {\frac {\alpha }{2}}} , on a A C = 1 + sin ⁡ α = 1 + 2 t 1 + t 2 {\displaystyle AC=1+\sin \alpha =1+{\frac {2t}{1+t^{2}}}} , sachant t = 1 − t 2 1 + t 2 {\displaystyle t={\frac {1-t^{2}}{1+t^{2}}}} . En éliminant t {\displaystyle t} , on obtient A C 3 − A C 2 − A C − 1 = 0 {\displaystyle AC^{3}-AC^{2}-AC-1=0} , ce qui montre que la constante de Tribonacci est égale à la longueur A C {\displaystyle AC} .

On a E C = τ ( τ − 1 ) ≈ 1 , 543689 {\displaystyle EC=\tau (\tau -1)\approx 1,543689} , voir la suite A256099 de l'OEIS.

L'angle α = B A C ^ {\displaystyle \alpha ={\widehat {BAC}}} vaut environ 57,065°.

Interprétation combinatoire de la suite de Tribonacci

Tn+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 T 4 = 4 {\displaystyle T_{4}=4} car 3 s'écrit 1 + 1 + 1   ; 1 + 2   ; 2 + 1   ; ou  3 {\displaystyle 1+1+1\ ;1+2\ ;2+1\ ;{\text{ou }}3} [6],[7].

De façon imagée, Tn+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 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
, celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de 
  
    
      
        n
        −
        2
      
    
    {\displaystyle n-2}
  
, celles se terminant par 3 sont obtenues en ajoutant 3 à la fin d'une composition de 
  
    
      
        n
        −
        3
      
    
    {\displaystyle n-3}
  
 , donc le nombre 
  
    
      
        
          C
          
            n
          
        
      
    
    {\displaystyle C_{n}}
  
 de composition de n vérifie 
  
    
      
        
          C
          
            n
          
        
        =
        
          C
          
            n
            −
            1
          
        
        +
        
          C
          
            n
            −
            2
          
        
        +
        
          C
          
            n
            −
            3
          
        
      
    
    {\displaystyle C_{n}=C_{n-1}+C_{n-2}+C_{n-3}}
  
. De plus, 
  
    
      
        
          C
          
            0
          
        
        =
        
          T
          
            1
          
        
        =
        1
      
    
    {\displaystyle C_{0}=T_{1}=1}
  
 (la composition vide), 
  
    
      
        
          C
          
            1
          
        
        =
        
          T
          
            2
          
        
        =
        1
      
    
    {\displaystyle C_{1}=T_{2}=1}
  
 (la composition (1)), 
  
    
      
        
          C
          
            2
          
        
        =
        
          T
          
            3
          
        
        =
        2
      
    
    {\displaystyle C_{2}=T_{3}=2}
  
 (les compositions (1,1) et (2)), ce qui montre la relation.

De manière plus générale[6], 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 0 , 1 , 2 , 3 , … , k − 1 {\displaystyle 0,1,2,3,\dots ,k-1} étant égaux à ( 0 , 1 , 1 , 2 , … , 2 k − 3 ) {\displaystyle \left(0,1,1,2,\dots ,2^{k-3}\right)} correspond au nombre de compositions de n formées à partir des entier de 1 à k.

Suite de mots 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 par concaténation des 3 mots précédents : la longueur du mot M(n) est donc égale à T n + 1 {\displaystyle T_{n+1}} .

Le mot infini obtenu à la limite est le mot infini de Tribonacci. C'est un mot purement morphique.

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

Autres suites remarquables ayant la récurrence de Tribonacci

1)

La suite définie par { T 0 ′ = 3 , T 1 ′ = 1 , T 2 ′ = 3 T n + 3 ′ = T n + 2 ′ + T n + 1 ′ + T n ′ {\displaystyle {\begin{cases}T'_{0}=3,T'_{1}=1,T'_{2}=3\\T'_{n+3}=T'_{n+2}+T'_{n+1}+T'_{n}\end{cases}}}  ; elle est la suite somme des puissances n-ièmes des racines de X 3 − X 2 − X − 1 {\displaystyle X^{3}-X^{2}-X-1}  :

T n ′ = τ n + r n + r ¯ n {\displaystyle T'_{n}=\tau ^{n}+r^{n}+{\overline {r}}^{n}} .

Premiers termes : 3, 1, 3, 7, 11, 21, 39, 71, 131,..., suite A001644 de l'OEIS. De r + r ¯ = 1 − τ , r r ¯ = 1 / τ {\displaystyle r+{\overline {r}}=1-\tau ,r{\overline {r}}=1/\tau } , on tire r = e i θ τ {\displaystyle r={\frac {\mathrm {e} ^{\mathrm {i} \theta }}{\sqrt {\tau }}}} où θ = arccos ⁡ ( − τ ( τ − 1 ) / 2 ) {\displaystyle \theta =\arccos(-{\sqrt {\tau }}(\tau -1)/2)} , d'où la formule :

T n ′ = τ n + 2 cos ⁡ n θ τ n {\displaystyle T'_{n}=\tau ^{n}+{\frac {2\cos n\theta }{\sqrt {\tau ^{n}}}}}

Et à partir de n = 4 {\displaystyle n=4}  :

T n ′ = ⌊ τ n ⌉ {\displaystyle T'_{n}=\lfloor \tau ^{n}\rceil } .


Expression à l'aide de la matrice compagnon de X 3 − X 2 − X − 1 {\displaystyle X^{3}-X^{2}-X-1}  :

T n ′ = Trace ⁡ ( [ 0 0 1 1 0 1 0 1 1 ] n ) . {\displaystyle T'_{n}=\operatorname {Trace} \left({\begin{bmatrix}0&0&1\\1&0&1\\0&1&1\end{bmatrix}}^{n}\right).}

Cette suite est à la suite de Tribonacci définie ci-dessus ce qu'est la suite de Perrin à la suite de Padovan ; elle possède la propriété arithmétique remarquable que si p {\displaystyle p} est premier, T p ′ − 1 {\displaystyle T'_{p}-1} est un multiple de p {\displaystyle p} .

Ceci peut être vu comme une application de la propriété de congruence pour les matrices à coefficients entiers : Trace ⁡ A p ≡ Trace ⁡ A mod p {\displaystyle \operatorname {Trace} A^{p}\equiv \operatorname {Trace} A\mod p} [8].

Le nombre n = 182 {\displaystyle n=182} est le plus petit composé n {\displaystyle n} tel que T n ′ − 1 {\displaystyle T'_{n}-1} soit un multiple de n {\displaystyle n} .

2)

La suite définie par { T 0 ″ = 1 , T 1 ″ = 1 , T 2 ″ = 1 T n + 3 ″ = T n + 2 ″ + T n + 1 ″ + T n ″ {\displaystyle {\begin{cases}T''_{0}=1,T''_{1}=1,T''_{2}=1\\T''_{n+3}=T''_{n+2}+T''_{n+1}+T''_{n}\end{cases}}} .

Premiers termes : 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355,..., suite A000213 de l'OEIS.

En fait, T n ″ = T n + 1 − T n − 1 {\displaystyle T''_{n}=T_{n+1}-T_{n-1}} .

3)

La suite définie par { T 0 ‴ = 0 , T 1 ‴ = 1 , T 2 ‴ = 0 T n + 3 ‴ = T n + 2 ‴ + T n + 1 ‴ + T n ‴ {\displaystyle {\begin{cases}T'''_{0}=0,T'''_{1}=1,T'''_{2}=0\\T'''_{n+3}=T'''_{n+2}+T'''_{n+1}+T'''_{n}\end{cases}}} .

Premiers termes :0, 1, 0, 1, 2, 3, 6, 11, 20, 37, 68, ..., suite A001590 de l'OEIS.

En fait, T n ‴ = T n − T n − 1 {\displaystyle T'''_{n}=T_{n}-T_{n-1}} .

Notes et références

  1. ↑ a et b (en) M. Feinberg, « Fibonacci-Tribonacci », Fibonacci Quarterly, no 1,‎ 1963., p. 71–74 (lire en ligne)
  2. ↑ (en) V. E. Jr. Hoggatt, « Additive partitions of the positive integers », Fibonacci Quarterly, vol. 18,‎ , p. 220-226 (zbMATH 0436.10009, lire en ligne).
  3. ↑ Voir la suite A058265 de l'OEIS.
  4. ↑ D.A. Wolfram, « Solving Generalized Fibonacci Recurrences », Fib. Quart.,‎ (lire en ligne)
  5. ↑ « Simon Plouffe », sur www.plouffe.fr (consulté le )
  6. ↑ a et b (en) John C. Baez, One-bonacci, Two-bonacci, Three-bonacci, Four..., 12/12/2003
  7. ↑ (en) Archit Boobna, Patrick Corn, Jimin Khim, « Tribonaci sequence »
  8. ↑ Francinou, Gianella, Nicolas, Oraux X-Ens, Algèbre 1, Cassini, , exercice 7.14

Voir aussi

Articles connexes

Liens externes

  • (en) Eric W. Weisstein, « Tribonacci Number », sur MathWorld
  • (en) Marie Lejeune, Michel Rigo et Matthieu Rosenfeld, « Templates for the k-binomial complexity of the Tribonacci word », Adv. Appl. Math., vol. 112,‎ , article no 101947 (DOI 10.1016/j.aam.2019.101947, lire en ligne).
  • icône décorative Portail des mathématiques