Tribonacci : ce qu'un élève de 14 ans a vu au-delà de Fibonacci

En octobre 1963, le troisième numéro d’une revue toute jeune, The Fibonacci Quarterly, publie un article de quatre pages signé Mark Feinberg. La note de la rédaction qui le précède précise qu’il a quatorze ans, qu’il est en ninth grade, l’équivalent de notre troisième, dans un collège de Pennsylvanie, et que son article reprend le projet qui vient de lui valoir le titre de grand champion de la Junior Academy of Science de Pennsylvanie.

Sa question est simple. Dans la suite de Fibonacci, chaque nombre est la somme des deux précédents. Que se passe-t-il si on additionne les trois précédents ? Il appelle cette nouvelle suite « Tribonacci ». D’autres l’avaient étudiée avant lui, dont le mathématicien Nikolaï Agronomov dès 1914, mais c’est sous le nom choisi par Feinberg que tout le monde la connaît aujourd’hui.

Pour moi, c’est l’une des meilleures façons de trouver un sujet de Grand oral : prendre une règle que tu connais, la modifier, et regarder ce qui se passe. Je repars de la question de Feinberg, et je la pousse un peu plus loin.

Monter un escalier

Tu dois monter un escalier, et à chaque pas tu peux franchir une, deux ou trois marches. De combien de façons différentes peux-tu monter un escalier de $n$ marches ?

Les mathématiciens appellent ça une composition. Soit $n \geq 1$ un entier. On appelle composition de $n$ en parts $1$, $2$ et $3$ toute suite finie $(a_1, a_2, \dots, a_r)$, avec $r \geq 1$, dont chaque terme $a_i$ vaut $1$, $2$ ou $3$, et dont la somme vaut $n$. L’ordre compte : pour $n = 3$, les suites $(1, 2)$ et $(2, 1)$ sont deux compositions différentes, comme deux manières distinctes de monter l’escalier.

Pour tout entier $n \geq 1$, on note $c_n$ le nombre de compositions de $n$. On pose aussi $c_0 = 1$ : il y a une seule façon de monter un escalier de zéro marche, celle qui consiste à ne pas bouger. Le simulateur ci-dessous liste toutes les façons pour un petit escalier.

Tu trouves $c_1 = 1$, $c_2 = 2$, $c_3 = 4$, $c_4 = 7$.

Pour les compter sans tout lister, regarde le premier pas. Soit $n \geq 3$ un entier. Une façon de monter $n$ marches commence par un pas de $1$, de $2$ ou de $3$ marches, et ce qui suit est une façon de monter les marches restantes. Il y a donc $c_{n-1}$ façons qui commencent par un pas de $1$, $c_{n-2}$ qui commencent par un pas de $2$ et $c_{n-3}$ qui commencent par un pas de $3$. Comme ces trois cas ne se recouvrent pas :

C’est là que la convention $c_0 = 1$ sert : pour $n = 3$, le pas de $3$ marches monte tout l’escalier d’un coup, et il compte pour une façon.

Si tu n’autorises que des pas de $1$ ou $2$ marches, le même raisonnement donne une relation à deux termes, et tu retombes sur la suite de Fibonacci. Essaie le bouton « Pas de 1 ou 2 » dans le simulateur : tu obtiens $1, 2, 3, 5, 8, \dots$ Fibonacci et Tribonacci sont donc deux versions du même problème d’escalier.

Pour la suite de Tribonacci, je garde la convention de l’article qui présente toute la série :

Ses premiers termes sont $0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149$. Ce sont les nombres de l’escalier, décalés de deux rangs. Tu vois d’où vient ce décalage ?

Propriété. Pour tout entier $n \geq 0$, on a $c_n = T_{n+2}$.

Démonstration. On raisonne par récurrence. Pour tout entier $n \geq 0$, on note $\mathcal{P}(n)$ la propriété :

Initialisation. On a $c_0 = 1 = T_2$, $c_1 = 1 = T_3$ et $c_2 = 2 = T_4$. Donc $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $n \geq 0$ un entier tel que $\mathcal{P}(n)$ soit vraie. Les deux premières égalités de $\mathcal{P}(n+1)$, à savoir $c_{n+1} = T_{n+3}$ et $c_{n+2} = T_{n+4}$, font déjà partie de $\mathcal{P}(n)$. Pour la troisième, on applique la relation de l’escalier au rang $n + 3 \geq 3$ :

La dernière égalité est la relation de récurrence de la suite de Tribonacci, au rang $n + 2$. Donc $\mathcal{P}(n+1)$ est vraie, et la propriété est démontrée pour tout entier $n \geq 0$.

Ce décalage de deux rangs est un piège classique. Selon les livres et les sites, la suite de Tribonacci commence par $0, 0, 1$, par $0, 1, 1$ ou par $1, 1, 2$. Feinberg lui-même la faisait commencer par $1, 1, 2$. Choisis une convention et annonce-la dès le début : si le jury te parle du décalage, tu auras la réponse.

Une constante qui n’est plus le nombre d’or

Pour Fibonacci, le quotient de deux termes consécutifs se rapproche du nombre d’or, $\varphi \approx 1{,}618$. Pour Tribonacci, je regarde le même quotient. Pour tout entier $n \geq 2$, le terme $T_n$ est strictement positif, et on peut poser :

Voici les premières valeurs :

Les quotients se resserrent autour d’une valeur proche de $1{,}839$. Tu devines de quelle équation elle sort ?

Supposons que la suite $(q_n)$ converge vers une limite $\ell$. Soit $n \geq 2$ un entier. On divise la relation $T_{n+3} = T_{n+2} + T_{n+1} + T_n$ par $T_n$, en utilisant :

On obtient :

En passant à la limite quand $n$ tend vers $+\infty$, on trouve :

C’est le calcul que fait Feinberg dans son article, sous une forme un peu différente. Encore faut-il savoir combien cette équation a de solutions réelles.

Propriété. L’équation $x^3 = x^2 + x + 1$ a une unique solution réelle. On la note $\tau$, on l’appelle la constante de Tribonacci, et elle vérifie $1{,}8 < \tau < 1{,}9$.

Démonstration. On étudie la fonction $f$ définie sur $\mathbb{R}$ par :

Elle est dérivable, et pour tout réel $x$ :

La fonction $f$ est donc croissante sur $\left]-\infty\,; -\dfrac{1}{3}\right]$, décroissante sur $\left[-\dfrac{1}{3}\,; 1\right]$ et croissante sur $[1\,; +\infty[$.

Pas de solution avant $1$. Sur $]-\infty\,; 1]$, le maximum de $f$ est atteint en $-\dfrac{1}{3}$, et il vaut :

Donc $f$ ne s’annule pas sur $]-\infty\,; 1]$.

Une seule solution après $1$. Sur $[1\,; +\infty[$, la fonction $f$ est continue et strictement croissante, avec :

D’après le théorème des valeurs intermédiaires, appliqué à une fonction strictement monotone, $f$ s’annule une seule fois sur $[1\,; +\infty[$, en un réel compris entre $1{,}8$ et $1{,}9$.

Une calculatrice donne $\tau \approx 1{,}839\,287$. Donc, si la suite $(q_n)$ converge, sa limite est $\tau$.

Feinberg ne donne de valeur décimale que pour le quotient d’un terme par le suivant : $0{,}543\,689\,01$, qui est l’inverse de $\tau$.

Ce raisonnement a un point faible, et c’est le deuxième piège de ce sujet : on a supposé que la suite $(q_n)$ converge. Feinberg fait la même chose : il affirme que la suite converge et que tous les quotients tendent vers une même valeur, sans le démontrer. La convergence est vraie, mais sa démonstration la plus directe dépasse le programme. Au Grand oral, tu l’admets, en disant clairement que c’est elle qui justifie le passage à la limite.

Pourquoi la convergence est vraie (pour aller plus loin). L’équation $x^3 = x^2 + x + 1$ a, en plus de $\tau$, deux solutions complexes conjuguées $z$ et $\overline{z}$. En développant $(x - \tau)(x - z)(x - \overline{z})$ et en identifiant avec $x^3 - x^2 - x - 1$, on trouve $\tau\,|z|^2 = 1$. Le module de $z$ et de $\overline{z}$, c’est-à-dire leur distance à $0$ dans le plan complexe, vaut donc $\dfrac{1}{\sqrt{\tau}} \approx 0{,}737$, qui est strictement inférieur à $1$. On peut démontrer, mais c’est hors programme, qu’il existe un réel $A > 0$ et un complexe $B$ tels que, pour tout entier $n \geq 0$ :

C’est l’analogue de la formule de Binet, qui exprime $F_n$ à l’aide de $\varphi$ pour Fibonacci. Comme $|z| < 1$, les deux derniers termes tendent vers $0$, le terme en $\tau^n$ l’emporte, et le quotient $q_n$ tend vers $\tau$.

Pour les élèves de maths expertes. On peut écrire la suite avec des matrices. Pour tout entier $n \geq 0$, on pose :

La relation de récurrence s’écrit alors, pour tout entier $n \geq 0$ :

Calculer un terme de la suite revient donc à calculer une puissance de matrice. Hors programme cette fois : si on note $I_3$ la matrice identité de taille $3$, un réel $\lambda$ rend la matrice $M - \lambda I_3$ non inversible exactement quand $\lambda^3 = \lambda^2 + \lambda + 1$. L’équation de Tribonacci réapparaît là aussi.

Additionner k termes, et la limite 2

Feinberg ne s’arrête pas à trois termes. À la fin de son article, il étudie la suite qui additionne les quatre termes précédents, qu’il appelle « Tetranacci », et il trouve que les quotients se rapprochent de $1{,}927\,561\,9$. Dans cet article de 1963, il s’arrête là. Je prends le relais.

Soit $k \geq 2$ un entier. On définit la suite $k$-bonacci $(u_n)$ par ses $k$ premiers termes et une relation de récurrence à $k$ termes :

Pour $k = 2$, c’est Fibonacci, pour $k = 3$, c’est Tribonacci, et pour $k = 4$, c’est la suite de Feinberg, à un décalage d’indices près. Pour tout entier $n \geq k - 1$, le terme $u_n$ est strictement positif, et on note encore $q_n = \dfrac{u_{n+1}}{u_n}$, avec la même notation que pour Tribonacci. Le même calcul que plus haut montre que, si la suite $(q_n)$ converge, sa limite est une solution de l’équation, qu’on note $(E_k)$ :

J’admets, comme pour Tribonacci, que la suite $(q_n)$ converge. Sa limite est au moins égale à $1$ : tous les termes de la suite sont positifs ou nuls, et pour tout entier $n \geq k - 1$, le terme $u_n$ fait partie de la somme qui définit $u_{n+1}$, donc $u_{n+1} \geq u_n$. Elle est aussi différente de $1$, puisque $1$ n’est pas solution de $(E_k)$ : le membre de gauche vaut alors $1$ et celui de droite $k \geq 2$. La limite est donc une solution de $(E_k)$ strictement supérieure à $1$. Je montre plus bas qu’il n’y en a qu’une, et on la notera $\tau_k$.

Choisis différentes valeurs de $k$ ci-dessous et regarde où se stabilisent les quotients.

Les limites montent vers $2$ sans jamais l’atteindre : on trouve $\tau_2 = \varphi \approx 1{,}618$, $\tau_3 = \tau \approx 1{,}839$, $\tau_4 \approx 1{,}928$, $\tau_5 \approx 1{,}966$. Une fois admise la convergence des quotients, tout le reste se démontre.

Propriété. Pour tout entier $k \geq 2$, l’équation $(E_k)$ a une unique solution $\tau_k$ strictement supérieure à $1$, et cette solution vérifie :

En particulier, $\tau_k$ tend vers $2$ quand $k$ tend vers $+\infty$.

Démonstration. Soit $k \geq 2$ un entier. Pour tout réel $x \neq 1$, la somme $x^{k-1} + \cdots + x + 1$ est la somme des termes d’une suite géométrique de raison $x$, et vaut $\dfrac{x^k - 1}{x - 1}$. Pour $x > 1$, l’équation $(E_k)$ équivaut donc, après multiplication par $x - 1 > 0$, à :

La fonction $g$ est dérivable sur $[1\,; +\infty[$, et pour tout réel $x \geq 1$ :

Unicité. Comme $k \geq 2$, on a $\dfrac{2k}{k+1} > 1$. La fonction $g$ est donc strictement décroissante sur $\left[1\,; \dfrac{2k}{k+1}\right]$ et strictement croissante sur $\left[\dfrac{2k}{k+1}\,; +\infty\right[$. Comme $g(1) = 0$, elle est strictement négative sur $\left]1\,; \dfrac{2k}{k+1}\right]$. Sur l’intervalle suivant, elle est continue et strictement croissante, elle part de $g\left(\dfrac{2k}{k+1}\right) < 0$ et elle tend vers $+\infty$ : elle s’annule une seule fois. L’équation $(E_k)$ a donc une unique solution $\tau_k > 1$, et pour tout réel $x > 1$, on a $g(x) < 0$ si $x < \tau_k$ et $g(x) > 0$ si $x > \tau_k$.

Encadrement. On calcule :

Comme $k \geq 2$, on a $\left(\dfrac{3}{2}\right)^k \geq \dfrac{9}{4} > 2$, donc $g\left(\dfrac{3}{2}\right) < 0 < g(2)$. D’après le signe de $g$ établi juste avant, on en déduit $\dfrac{3}{2} < \tau_k < 2$.

Limite. L’égalité $g(\tau_k) = 0$ s’écrit :

Comme $\left(\dfrac{2}{3}\right)^k$ tend vers $0$ quand $k$ tend vers $+\infty$, d’après le théorème des gendarmes, $\tau_k$ tend vers $2$.

En plus, ces limites augmentent avec $k$. Si on note $g_k$ la fonction $g$ associée à l’entier $k$, l’égalité $\tau_k^{\,k}\,(\tau_k - 2) = -1$ donne :

et le signe de $g_{k+1}$ donne $\tau_k < \tau_{k+1}$.

J’aime beaucoup ce résultat, parce qu’il remet le nombre d’or à sa place : dans cette famille, $\varphi$ est simplement la première d’une série de constantes qui montent vers $2$, toutes solutions du même type d’équation.

Le triangle trinomial

Tu connais peut-être une propriété du triangle de Pascal : en additionnant les nombres le long de certaines diagonales, celles qui montent en pente douce, on obtient les nombres de Fibonacci. Tribonacci a son propre triangle.

Pour tout entier $n \geq 0$, on développe $(1 + x + x^2)^n$ et on note $a(n, k)$ le coefficient de $x^k$, pour tout entier $k$ compris entre $0$ et $2n$. On pose $a(n, k) = 0$ pour les autres valeurs de $k$. Le triangle trinomial est le tableau de ces coefficients, la ligne $n$ contenant $a(n, 0), a(n, 1), \dots, a(n, 2n)$.

Comme $(1 + x + x^2)^{n+1} = (1 + x + x^2)^n (1 + x + x^2)$, on a, pour tout entier $n \geq 0$ et tout entier $k$ :

Dans le triangle, chaque nombre est donc la somme des trois nombres placés juste au-dessus de lui, comme dans le triangle de Pascal, où l’on n’en additionne que deux.

Propriété. Pour tout entier $m \geq 0$, la somme des coefficients $a(n, k)$ tels que $n + k = m$ vaut $T_{m+2}$ :

Démonstration. Soient $n \geq 0$ et $k$ deux entiers. Quand on développe le produit des $n$ facteurs $(1 + x + x^2)$, on choisit dans chaque facteur l’un des termes $1$, $x$ ou $x^2$, c’est-à-dire un exposant $0$, $1$ ou $2$. Le coefficient $a(n, k)$ compte donc les suites de $n$ nombres, chacun égal à $0$, $1$ ou $2$, dont la somme vaut $k$.

Pour $m = 0$, la somme se réduit à $a(0, 0) = 1 = T_2$. Pour $m \geq 1$, le terme $n = 0$ est nul, car $a(0, m) = 0$, et on classe les compositions de $m$ selon leur nombre $n$ de parts, compris entre $1$ et $m$.

Soit $n$ un entier compris entre $1$ et $m$. Prenons une composition de $m$ en exactement $n$ parts $1$, $2$ ou $3$, et retirons $1$ à chaque part : on obtient une suite de $n$ nombres égaux à $0$, $1$ ou $2$, de somme $m - n$. Inversement, en ajoutant $1$ à chaque terme d’une telle suite, on retrouve la composition de départ. Le nombre de compositions de $m$ en $n$ parts est donc $a(n, m - n)$. En additionnant sur tous les nombres de parts possibles, de $1$ à $m$, on obtient le nombre total de compositions de $m$, c’est-à-dire $c_m = T_{m+2}$.

Le triangle trinomial, c’est donc le problème de l’escalier, rangé selon le nombre de pas. Feinberg l’avait vu lui-même : un an après son premier article, il publie dans la même revue un second texte, New Slants, où il construit ce triangle et remarque que ses diagonales donnent la suite de Tribonacci.

Le snub cube

C’est l’apparition de $\tau$ que je trouve la plus surprenante : elle fixe la forme d’un polyèdre, le snub cube, qu’on appelle cube adouci en français. Kepler l’a décrit en 1619 sous le nom latin de cubus simus. C’est un polyèdre à $24$ sommets, $60$ arêtes et $38$ faces : $6$ carrés et $32$ triangles équilatéraux. Toutes ses arêtes ont la même longueur, et tous ses sommets jouent le même rôle, ce qui en fait l’un des treize polyèdres archimédiens. Il a une particularité : il existe en deux versions, images l’une de l’autre dans un miroir, comme une main gauche et une main droite.

On peut décrire ses sommets avec des coordonnées. Soit $t > 1$ un réel. On part du triplet $\left(1, \dfrac{1}{t}, t\right)$, et on range ses trois nombres dans un ordre ou un autre. Trois de ces ordres s’obtiennent en faisant tourner le triplet, on les appelle les permutations circulaires :

Les trois autres ordres échangent deux nombres. On donne ensuite des signes aux trois coordonnées, avec une règle : pour les trois ordres circulaires, le nombre de signes $+$ doit être pair, et pour les trois autres, il doit être impair. Par exemple, $\left(-1, -\dfrac{1}{t}, -t\right)$ a zéro signe $+$, donc tu le gardes. On obtient ainsi $24$ points, et la question est de choisir $t$ pour que ces points soient les sommets d’un polyèdre dont toutes les arêtes ont la même longueur.

Regarde le sommet $P$ et trois de ses voisins :

Les arêtes du snub cube sont de trois types, et ces trois segments en donnent un exemple de chaque. Le segment $[PR]$ borde un carré. Le segment $[PQ]$ est un côté de l’un des $8$ triangles centrés sur une diagonale du cube, qui ne partagent aucune arête avec un carré. Le segment $[PS]$, lui, n’appartient ni à un carré ni à l’un de ces $8$ triangles : il est commun à deux des $24$ autres triangles. J’admets que, pour tout $t > 1$, les arêtes se répartissent bien en ces trois types : la figure le montre pour $t = \tau$, et un calcul à l’ordinateur le confirme pour les autres valeurs. On calcule les carrés de leurs longueurs :

Les arêtes $[PQ]$ et $[PR]$ ont la même longueur si et seulement si :

La dernière équivalence s’obtient en multipliant par $t$, qui est strictement positif. Les arêtes $[PS]$ et $[PR]$, elles, ont la même longueur si et seulement si :

La deuxième équivalence s’obtient en divisant par $2$, puis en multipliant par $t^2 > 0$. Comme $t > 1$, on retombe sur la même équation. Les deux conditions donnent donc $t^3 = t^2 + t + 1$, dont la seule solution réelle est $\tau$. Avec $t = \tau$, les $60$ arêtes ont toutes la même longueur, environ $1{,}61$ avec ces coordonnées. Les arêtes d’un même type ont bien toutes la même longueur : les transformations $(x, y, z) \mapsto (y, z, x)$ et $(x, y, z) \mapsto (-y, x, z)$ envoient les $24$ points sur eux-mêmes en conservant les distances, et en les combinant, on envoie n’importe quelle arête sur n’importe quelle autre arête du même type. Ce dernier point, on l’admet ou on le vérifie à l’ordinateur.

Ce calcul prend un demi-tableau : je te conseille de le garder pour l’échange, si le jury te demande d’où sort $\tau$ dans le snub cube.

Refaire le chemin de Feinberg

Moi, je construirais l’oral comme une suite de questions, celles que Feinberg s’est posées en modifiant une règle. Pour chaque étape, je précise ce que tu démontres et ce que tu admets.

1. Que se passe-t-il si on additionne trois termes au lieu de deux ? Tu poses le problème de l’escalier, tu établis la relation de récurrence et tu démontres que les compositions sont comptées par la suite de Tribonacci. Ici, tout se démontre.
2. Le quotient de deux termes consécutifs converge-t-il encore, et vers quoi ? Tu montres que la limite, si elle existe, est solution de $x^3 = x^2 + x + 1$, puis tu démontres que cette équation a une seule solution réelle. Tu admets la convergence, en le disant.
3. Et si on additionne $k$ termes ? Tu démontres l’encadrement $0 < 2 - \tau_k < \left(\dfrac{2}{3}\right)^k$ et la limite $2$, avec une étude de fonction et le théorème des gendarmes. La convergence des quotients, elle, reste admise.
4. Où retrouve-t-on cette constante ? Tu choisis le triangle trinomial ou le snub cube, mais pas les deux : ton exposé est court, et un seul prolongement bien traité vaut mieux que deux survolés. L’autre peut venir pendant l’échange avec le jury.

Côté programme, tu restes en terrain connu : les suites définies par récurrence, le raisonnement par récurrence, l’étude de fonctions, le théorème des valeurs intermédiaires, les limites, le dénombrement, et les matrices si tu suis les maths expertes. Pendant les vingt minutes de préparation, écris sur ton brouillon les premiers termes de la suite et le tableau de variations de $f$ : ce sont les deux points que tu dois savoir refaire sans hésiter pendant l’échange.

Ce que Feinberg a laissé de côté

En 1963, Feinberg avait fait l’essentiel : changer une règle, calculer, trouver une constante et en chercher l’équation. Il est même allé jusqu’à quatre termes, et un an plus tard, il a relié lui-même sa suite au triangle trinomial. Dans son article de 1963, en revanche, il ne parle ni de la limite $2$, ni du snub cube. La limite $2$, tu la démontres ; pour le prolongement, choisis le triangle ou le polyèdre. Dans les deux cas, ton oral ira plus loin que l’article d’un collégien de 1963.

Pour comparer avec les autres angles de la série :

• l’article qui présente toute la série ;
• le théorème de Lamé ;
• le théorème de Zeckendorf ;
• les tournesols et l’angle d’or.

Tous les autres sujets sont rassemblés sur la page Grand oral.

Sources

• Agronomof, N. (1914). Sur une suite récurrente. Mathesis, 4e série, tome 4, pp. 125-126.
• Miles, E. P., Jr. (1960). Generalized Fibonacci Numbers and Associated Matrices. The American Mathematical Monthly, 67(8), pp. 745-752.
• Feinberg, M. (1963). Fibonacci-Tribonacci. The Fibonacci Quarterly, 1(3), pp. 71-74.
• Feinberg, M. (1964). New Slants. The Fibonacci Quarterly, 2(3), pp. 223-227.
• Hoggatt, V. E., Jr. et Bicknell, M. (1969). Diagonal Sums of Generalized Pascal Triangles. The Fibonacci Quarterly, 7(4), pp. 341-358.
• Hoggatt, V. E., Jr. et Bicknell, M. (1974). Diagonal Sums of the Trinomial Triangle. The Fibonacci Quarterly, 12(1), pp. 47-50.
• OEIS : suite A000073 (nombres de Tribonacci) et suite A027907 (triangle trinomial).
• Weisstein, E. W. Snub Cube et Tribonacci Constant. MathWorld, Wolfram Research.