Voici l’arbre de Calkin-Wilf. C’est un arbre binaire rempli de fractions et possédant des propriétés fascinantes.
Les premières générations sont représentées. L’arbre est infini. La règle pour construire l’arbre est simple. La racine de l’arbre est \(\frac{1}{1}\). Chaque fraction \(\frac{a}{b}\) est un parent unique de deux enfants : l’enfant de gauche \(\frac{a}{a+b}\) et l’enfant de droite \(\frac{a+b}{b}\).
Sachant que \(a\geq 1\) et \(b\geq 1\), il est clair que l’enfant de gauche est une fraction strictement comprise entre \(0\) et \(1\) car \(a<a+b\) et que l’enfant de droite est une fraction supérieure à \(1\) car \(a+b>b\).
Un coup d’œil à l’arbre suggère que les fractions qui y apparaissent sont irréductibles. C’est le cas. En effet, si \(a\) et \(b\) sont premiers entre eux, alors \(a\) ne partage aucun facteur premier avec \(a+b\) et \(b\) ne partage aucun facteur premier avec \(a+b\). Les fractions \(\frac{a}{a+b}\) et \(\frac{a+b}{b}\) sont réduites. Cela ne serait évidemment pas le cas si \(a\) et \(b\) partageaient un facteur premier commun. Or, puisque la racine de l’arbre est la fraction \(\frac{1}{1}\), dans laquelle le numérateur et le dénominateur ne partagent aucun facteur premier, cela n’engendre par la suite effectivement que des fractions irréductibles.
Une même fraction peut-elle apparaître à plusieurs endroits dans l’arbre ? Est-ce que toutes les fractions apparaissent dans l’arbre ?
Considérons une fraction \(\frac{a}{b}\). Apparaît-elle dans l’arbre ? Si oui, elle est soit un enfant de gauche ou un enfant de droite. Il suffit de vérifier si \(\frac{a}{b}\) est une fraction impropre ou non. En d’autres mots, si \(a<b\), alors la fraction est un enfant de gauche. Son parent est la fraction \(\frac{a^{\prime}}{b^{\prime}}\) dans laquelle \(a^{\prime} = a\geq 1\) et \(b^{\prime} = b-a\geq 1\). Et si \(a>b\), \(\frac{a}{b}\) est un enfant de droite et son parent est la fraction \(\frac{a^{\prime}}{b^{\prime}}\) dans laquelle \(a^{\prime} = a-b\geq 1\) et \(b^{\prime} = b\geq 1\). On se pose ensuite la même question : la fraction \(\frac{a^{\prime}}{b^{\prime}}\) qui est égale à \(\frac{a}{b-a}\) ou \(\frac{a-b}{b}\) est-elle un enfant de gauche ou un enfant de droite ? On détermine ensuite son parent. Et on poursuit de la même manière… Mais ce processus ne peut perdurer indéfiniment. En effet à chaque étape (chaque fois qu’on trouve le parent de \(\frac{a}{b}\)) soit le dénominateur diminue (si \(\frac{a}{b}\) est un enfant de gauche, le dénominateur de son parent est \(b-a\) et \(b-a < b\)), soit le numérateur diminue (si \(\frac{a}{b}\) est un enfant de droite, le numérateur de son parent est \(a-b\) et \(a-b<a\)). Cela nous assure d’atteindre tôt ou tard la fraction \(\frac{1}{1}\). Et il suffit de faire le chemin dans le sens inverse pour obtenir celui qui mène de \(\frac{1}{1}\) à \(\frac{a}{b}\). Dans ce cas-ci, un exemple numérique s’impose.
La fraction irréductible \(\frac{11}{35}\) se trouve-t-elle dans l’arbre ? Bien sûr. Et voici comment atteindre \(\frac{11}{35}\) à partir de \(\frac{1}{1}\). La fraction \(\frac{11}{35}\) est est un enfant de gauche car \(0<\frac{11}{35}<1\). Son parent est \(\frac{11}{35-11} = \frac{11}{24}\). La fraction \(0<\frac{11}{24}<1\) est aussi un enfant de gauche et son parent est \(\frac{11}{24-11} = \frac{11}{13}\). La fraction \(0<\frac{11}{13}<1\) est également un enfant de gauche, son parent étant \(\frac{11}{13-11} = \frac{11}{2}\). La fraction \(\frac{11}{2}\) est aussi dans l’arbre, c’est un enfant de droite, car cette fois-ci \(\frac{11}{2}>1\). Son parent est \(\frac{11-2}{2} = \frac{9}{2}\). À nouveau \(\frac{9}{2}>1\) est un enfant de droite, on obtient ensuite des enfants de droite pendant quelques étapes : le parent de \(\frac{9}{2}\) est \(\frac{9-2}{2} =\frac{7}{2}\) ; celui de \(\frac{7}{2}>1\) est \(\frac{7-2}{2} = \frac{5}{2}\) ; celui de \(\frac{5}{2}>1\) est \(\frac{5-2}{2}= \frac{3}{2}\) ; celui que \(\frac{3}{2}>1\) est \(\frac{3-2}{2} = \frac{1}{2}\). Enfin, ultime étape, la fraction \(\frac{1}{2}<1\) est un enfant de gauche, son parent étant \(\frac{1}{2-1} = \frac{1}{1}\). On se retrouve à la racine de l’arbre. On a donc retrouvé le chemin qui mène de \(\frac{1}{1}\) à \(\frac{11}{35}\), il suffit de revenir sur nos pas (en partant de \(\frac{1}{1}\), si \(\text{G}\) représente « emprunter la branche de gauche » et \(\text{D}\) représente « emprunter la branche de droite », alors le chemin en question ici est \(\text{GDDDDDGGG}\)).\[\frac{1}{1}\underset{\textrm{G}}{\longrightarrow} \frac{1}{2}\underset{\textrm{D}}{\longrightarrow} \frac{3}{2}\underset{\textrm{D}}{\longrightarrow}\frac{5}{2}\underset{\textrm{D}}{\longrightarrow}\frac{7}{2}\underset{\textrm{D}}{\longrightarrow}\frac{9}{2}\underset{\textrm{D}}{\longrightarrow}\frac{11}{2}\underset{\textrm{G}}{\longrightarrow}\frac{11}{13}\underset{\textrm{G}}{\longrightarrow}\frac{11}{24}\underset{\textrm{G}}{\longrightarrow}\frac{11}{35}\]
Puisque toutes les fractions réduites apparaissent une unique fois dans l’arbre, celui-ci peut être utilisé comme système numérique pour représenter les nombres rationnels strictement positifs. Le nombre \(\frac{11}{35}\) est \(\text{GDDDDDGGG}\) et le nombre \(\frac{7}{3}\) est \(\text{GGDD}\) et \(\frac{3}{2}\) est \(\text{GD}\). Le nombre \(\frac{1}{1}\) étant la racine de l’arbre, il peut avoir son propre symbole.
\(\textcolor[RGB]{0,0,255}{\dfrac{7}{3}} = \textcolor[RGB]{0,0,255}{\textrm{ GGDD}}\)
N’est-ce pas extraordinaire ? Et puisque toutes les fractions réduites se trouvent dans l’arbre, il est possible de dresser une liste des nombres rationnels strictement positifs en parcourant chaque génération de l’arbre, de gauche à droite. La liste des rationnels obtenue est \[\left\{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \ \dots \right\}\]Soyons clairs : cette liste contient tous les nombres rationnels strictement positifs dans un ordre bien précis. Si on s’intéresse à la dénombrabilité des rationnels, c’est fort utile : on a une correspondance bien explicite entre les rationnels strictement positifs et les nombres naturels strictement positifs. Et à mon avis, c’est plus fin que les démonstrations habituelles du genre
dans lesquelles on obtient plusieurs fois le même nombre rationnel qu’on doit par la suite ignorer (par exemple, en associant le couple \((x,y)\) à la fraction \(\frac{x}{y}\), les couples \((1,2)\), \((2,4)\), \((3,6)\), etc. génèrent tous la fraction \(\frac{1}{2}\)) ou des absurdités (le couple \((3, 0)\) génère la fraction \(\frac{3}{0}\)).
Ainsi, chaque fraction a une position bien définie dans la liste. La \(5^{\textrm{e}}\) fraction est \(\frac{3}{2}\). La fraction \(\frac{7}{3}\) est à la \(19^{\textrm{e}}\) position. Ces deux fractions données en exemple apparaissent dans l’arbre illustré ci-haut, on peut donc compter manuellement leur position, mais il serait intéressant de connaître la position d’une fraction quelconque dans la liste et inversement, de connaître la fraction se trouvant à une position arbitraire. Par exemple, à quelle position se trouve la fraction \(\frac{13}{81}\) ? Quelle fraction se trouve à la \(101^{\textrm{e}}\) position ? À la \(2\,026^{\textrm{e}}\) position ? Pour répondre à cette question, considérons d’abord un autre arbre avec cette fois-ci la position dans la liste de chaque fraction.
On remarque que dans cet arbre, l’enfant de gauche est le double de son parent et l’enfant de droite est l’enfant de gauche augmenté de \(1\) (en d’autres mots c’est le double de son parent augmenté de \(1\)). En écrivant les nombres en base \(2\) quelque chose d’intéressant se produit : pour doubler un nombre, il suffit d’ajouter un \(0\) à la fin ce celui-ci. Et si on veut obtenir le double d’un nombre augmenté de \(1\), il suffit d’ajouter un \(1\) à la fin de celui-ci.
Ainsi, notre « système numérique » pour écrire les nombres rationnels n’est autre façon que d’écrire leur position dans la liste en binaire. En effet, chaque emprunt de la branche de gauche, \(\textrm{G}\), se traduit littéralement par un \(0\) et chaque emprunt de la branche de droite, \(\textrm{D}\), se traduit par un \(1\). En d’autres mots, la fraction donnée en exemple plus haut, \(\frac{11}{35}\), qu’on a exprimé comme \(\text{GDDDDDGGG}\) précédemment se trouve à la position \(1\,011\,111\,000_{2}\) dans la liste. On note qu’en plus de remplacer chaque \(\textrm{G}\) par un \(0\) et chaque \(\textrm{D}\) par un \(1\), on a en plus rajouté un \(1\) au tout début du nombre, qui correspond au point de départ, la racine \(\frac{1}{1}\) (en d’autres mots, on n’emprunte pas la première branche depuis le vide, on emprunte cette branche à partir de la première fraction de la liste, celle à la position \(1\)). Puisque \(1\,011\,111\,000_{2} = 8+16+32+64+128+512 = 760\), la fraction \(\frac{11}{35}\) occupe la \(760^{\textrm{e}}\) position dans la liste. Je suis bien heureux de ne pas avoir eu à étendre l’arbre jusqu’à avoir \(760\) fractions !
On précédemment constaté que la fraction \(\frac{3}{2}\) était la \(5^{\text{e}}\) fraction de la liste et son chemin était \(\textrm{GD}\). Or \(101_{2} = 4 + 1 = 5\). La fraction \(\frac{7}{3}\) était la \(19^{\textrm{e}}\) fraction de la liste et son chemin était \(\textrm{GGDD}\). On constate avec plaisir que \(10\,011_{2} = 16 + 2 + 1 = 19\).
\(\textcolor[RGB]{0,0,255}{\frac{7}{3}}\) est la \(\textcolor[RGB]{0,0,255}{10\,011_{2}}=\textcolor[RGB]{0,0,255}{19}^{\textrm{e}}\) fraction de l’arbre.
Quelle fraction occupe la \(101^{\textrm{e}}\) position ? Puisque \(101 = 1\,100\,101_{2}\), il est possible d’ignorer le premier \(1\) et de traduire chaque \(0\) par un \(\textrm{G}\) et chaque \(1\) par un \(\textrm{D}\). Son chemin est \(\textrm{DGGDGD}\) et la fraction est une fraction impropre car le chemin se termine par \(\textrm{D}\). Il suffit de quelques calculs pour trouver la valeur cherchée \[\frac{1}{1}\underset{\textrm{D}}{\longrightarrow} \frac{2}{1}\underset{\textrm{G}}{\longrightarrow} \frac{2}{3}\underset{\textrm{G}}{\longrightarrow}\frac{2}{5}\underset{\textrm{D}}{\longrightarrow}\frac{7}{5}\underset{\textrm{G}}{\longrightarrow}\frac{7}{12}\underset{\textrm{D}}{\longrightarrow}\frac{19}{12}\]La \(101^{\textrm{e}}\) fraction est \(\frac{19}{12}\).
Quelle fraction occupe la \(2\,026^{\textrm{e}}\) position ? Puisque \[2\,026 = 11\,111\,101\,010_{2}\]on connaît son chemin \(DDDDDGDGDG\). On sait d’emblée que la fraction sera une fraction propre puisque la séquence se termine par \(\textrm{G}\) et pour connaître sa valeur on effectue quelques calculs : \[\frac{1}{1}\underset{\textrm{D}}{\longrightarrow} \frac{2}{1}\underset{\textrm{D}}{\longrightarrow} \frac{3}{1}\underset{\textrm{D}}{\longrightarrow}\frac{4}{1}\underset{\textrm{D}}{\longrightarrow}\frac{5}{1}\underset{\textrm{D}}{\longrightarrow}\frac{6}{1}\underset{\textrm{G}}{\longrightarrow}\frac{6}{7}\underset{\textrm{D}}{\longrightarrow}\frac{13}{7}\underset{\textrm{G}}{\longrightarrow}\frac{13}{20}\underset{\textrm{D}}{\longrightarrow}\frac{33}{20}\underset{\textrm{G}}{\longrightarrow}\frac{33}{53}\]La \(2\,026^{\textrm{e}}\) fraction est \(\frac{33}{53}\).
Il existe cependant une manière plus élégante et plus simple de calculer la valeur de la fraction à partir de sa position dans la liste.
En effet, si \(x = \frac{a}{b}\) est le parent, l’enfant de gauche est \[\frac{a}{a + b} = \frac{\frac{a}{b}}{\frac{a+b}{b}} = \frac{x}{\frac{a}{b}+\frac{b}{b}} = \frac{x}{x+1} = \frac{\frac{x}{x}}{\frac{x+1}{x}} = \frac{1}{1+\frac{1}{x}}\]et l’enfant de droite est \[\frac{a+b}{b} = \frac{a}{b} + \frac{b}{b} = x + 1\]
Si on emprunte deux branches de gauche de suite on obtient : \begin{align*}x \underset{\textrm{G}}{\longrightarrow}\frac{1}{1+\frac{1}{x}}\underset{\textrm{G}}{\longrightarrow} \cfrac{1}{1+\cfrac{1}{\cfrac{1}{1+\cfrac{1}{x}}}}&=\cfrac{1}{1+\cfrac{1}{\cfrac{1}{\cfrac{x+1}{x}}}} \\ \\ &= \cfrac{1}{1+\cfrac{1}{\cfrac{x}{x+1}}} \\ \\ &= \cfrac{1}{1+\cfrac{x+1}{x}}\\ \\ &= \cfrac{1}{1+\cfrac{x}{x} + \cfrac{1}{x}} \\ \\ &= \cfrac{1}{1+1+\cfrac{1}{x}}\\ \\ &=\cfrac{1}{2+\cfrac{1}{x}}\end{align*}et si on emprunte \(n\) branches de gauche de suite, on obtient \[x \underset{\textrm{G } n \textrm{ fois}}{\longrightarrow} \cfrac{1}{n + \cfrac{1}{x}}\]Pour les branches de droite c’est plus simple. Si on emprunte deux branches de droite de suite on obtient \[x \underset{\textrm{D}}{\longrightarrow} x+1\underset{\textrm{D}}{\longrightarrow} (x+1)+1 = x+2\]Si on emprunte \(n\) branches de droite de suite on obtient \[x\underset{\textrm{D } n \textrm{ fois}}{\longrightarrow} = x + n\]
Ainsi il est possible de réduire le nombres d’étapes lorsqu’il y a plusieurs \(\textrm{G}\) ou \(\textrm{D}\) de suite en utilisant la fraction continue du nombre. Reprenons l’exemple de \(\frac{11}{35}\). Le chemin est \(\text{GDDDDDGGG}\) et c’est donc la \(1\,011\,111\,000_{2} = 760^{\textrm{e}}\) fraction de la liste. On obtient la fraction continue \[a_{0}+\cfrac{1}{a_{1}+ \cfrac{1}{a_{2}+\cfrac{1}{\dots \ + \cfrac{1}{a_{n}}}}}\] en comptant le nombre de \(1\) consécutifs à la fin du nombre pour obtenir \(a_{0}\), puis le nombre de \(0\) consécutifs pour obtenir \(a_{1}\), puis le nombre de \(1\) consécutifs pour obtenir \(a_{2}\) et ainsi de suite. Dans notre exemple, le nombre ne se termine par aucun \(1\), on trouve donc que \(a_{0} = 0\), ce qui est sensé sachant que \(\frac{11}{35}\) est une fraction propre. \[1\,011\,111\,000 = \underset{a_{4}=1}{\underbrace{1}}\,\underset{a_{3}=1}{\underbrace{0}}\,\underset{a_{2}=5}{\underbrace{11111}}\,\underset{a_{1}=3}{\underbrace{000}}\,\underset{a_{0}=0}{\underbrace{\phantom{1}}}\]Cela implique que \begin{align*}0 + \cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{1+\cfrac{1}{1}}}} &= 0 + \cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{2}}} \\ \\ &= 0 + \cfrac{1}{3+\cfrac{1}{\frac{11}{2}}} \\ \\ &= 0 + \cfrac{1}{3+\cfrac{2}{11}} \\ \\ &= 0 + \cfrac{1}{\frac{35}{11}} \\ \\ &= 0 + \frac{11}{35} \\ \\ &= \frac{11}{35}\end{align*}On peut considérer le deuxième exemple suivant, en reprenant celui de la fraction \(\frac{19}{12}\). C’était la \(101^{\textrm{e}}\) fraction. On sait que \[101 = 1\,100\,101_{2}\]On peut trouver les valeurs de \(a_{0}\), \(a_{1}\), etc.\[1\,100\,101 = \underset{a_{4}=2}{\underbrace{11}}\,\underset{a_{3}=2}{\underbrace{00}}\,\underset{a_{2}=1}{\underbrace{1}}\,\underset{a_{1}=1}{\underbrace{0}}\,\underset{a_{0}=1}{\underbrace{1}}\]On obtient \begin{align*}1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2}}}}&=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{\cfrac{5}{2}}}} \\ \\ &= 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{2}{5}}}\\ \\ &=1+\cfrac{1}{1+\cfrac{1}{\cfrac{7}{5}}} \\ \\ &=1+\cfrac{1}{1+\cfrac{5}{7}} \\ \\ &=1+\cfrac{1}{\cfrac{12}{7}}\\ \\ &= 1+\cfrac{7}{12} \\ \\ &=\frac{19}{12}\end{align*}
Il arrive, lorsque la position du nombre débute par \(10\dots\), comme c’est le cas avec \(\frac{11}{35}\), que la dernière valeur de la fonction continue, \(a_{n}\), est \(1\), ce qu’on essaie d’éviter habituellement lorsqu’on écrit ces fractions. Ce n’est pas anodin car si on veut effectuer le chemin inverse, et partir de la fraction continue pour obtenir la position dans l’arbre ou dans la liste, il faut considérer qu’un nombre en base \(2\) doit absolument commencer par \(1\). Puisque \(a_{0}\) compte le nombre de \(1\) à la fin de la position en binaire, \(n\) dans \(a_{n}\) doit être pair pour que \(a_{n}\) puisse aussi compter un nombre de \(1\). Par exemple, la fraction continue \[2+\cfrac{1}{3+\cfrac{1}{1+\cfrac{1}{4+\cfrac{1}{5}}}}=\frac{224}{99}\]ne pose pas de problème. La fraction étant impropre, on sait que \(a_{0} = 2\) compte le nombre de \(1\) qui se trouve à la fin de la position en binaire. Cela voudrait dire que \(a_{1}=3\) compte un nombre de \(0\), \(a_{2} = 1\) compte un nombre de \(1\), \(a_{3} = 4\) compte un nombre de \(0\) et \(a_{4} = 5\) compte un nombre de \(1\). La position en binaire commence donc par \(5\) chiffres \(1\) de suite. La position de la fraction \(\frac{224}{99}\) est donc la\[111\,110\,000\,100\,011_{2} = 31\,779^{\textrm{e}}\]de la liste. En revanche, la fraction continue \[1+\cfrac{1}{2+\cfrac{1}{4+\cfrac{1}{3}}} = \frac{42}{29}\]est problématique. En effet, c’est aussi une fraction impropre, sa position se termine par un \(1\), \(a_{0} =1\). Cela implique que \(a_{1}=2\) compte un nombre de \(0\), \(a_{2} = 4\) compte un nombre de \(1\) et \(a_{3} = 3\) compte un nombre de \(0\). Or, un nombre en base \(2\) ne peut commencer par \(0\), il doit commencer par \(1\). On note que \(n=3\), un nombre impair, et que cela avait été anticipé. Il faut donc réécrire la fraction continue comme \[1+\cfrac{1}{2+\cfrac{1}{4+\cfrac{1}{2 + \cfrac{1}{1}}}}\]Ainsi, on obtient \(a_{3}=2\), un nombre de \(0\) et \(a_{4} =1\), un nombre de \(1\). La position en binaire peut commencer par un \(1\) et cette position est la\[1\,001\,111\,001_{2} = 633^{\textrm{e}}\]de la liste. Comme dernier exemple, considérons la fraction continue \[0+\cfrac{1}{2 + \cfrac{1}{3+\cfrac{1}{4}}} = \frac{13}{30}\]Encore une fois, il faudra ici réécrire car \(n=3\). \[0+\cfrac{1}{2 + \cfrac{1}{3+\cfrac{1}{3+\cfrac{1}{1}}}} = \frac{13}{30}\]La fraction \(\frac{13}{30}\) est une fraction propre, \(a_{0}=0\) compte le nombre de \(1\) qui complète la position en binaire, \(a_{1}=2\) compte un nombre de \(0\), \(a_{2}=3\) compte un nombre de \(1\). Si on avait laissé \(a_{3} = 4\) cela aurait compté un nombre de \(0\), impossible. On considère plutôt \(a_{3} = 3\) pour le nombre de \(0\) et \(a_{4} =1\) pour le nombre de \(1\). La position de \(\frac{13}{30}\) est donc la \[100\,011\,100_2 = 284^{\textrm{e}}\]de la liste.
Est-il possible de déterminer quelle fraction suit une autre fraction dans l’arbre (ou dans la liste) ? Encore une fois, on peut répondre par l’affirmative. Il suffit de faire un peu de généalogie et de se rappeler que l’enfant de gauche de \(x\) est \(\frac{1}{1+\frac{1}{x}} = \frac{x}{1+x}\) et l’enfant de droite de \(x\) est \(x + 1\).
Considérons une fraction \(x\) et la fraction \(z\) qui suit \(x\). Pour trouver une expression correspondant à \(z\), on doit d’abord déterminer leur ancêtre commun. Appelons cet ancêtre commun \(y\). Si \(x\) est un enfant de gauche, c’est simple, \(y\) est son parent, donc \(x = \frac{y}{1+y}\) et la fraction suivante est l’enfant de droite de \(y\), c’est-à-dire que \(z = y + 1\).
Autrement, \(x\) est le \(k^{\textrm{e}}\) enfant de droite de l’enfant de gauche de \(y\) et \(z\), la fraction qui suit \(x\), est le \(k^{\textrm{e}}\) enfant de gauche de l’enfant de droite de \(y\).
Puisque l’enfant de gauche de \(y\) est \(\frac{y}{1+y}\), le \(k^{\textrm{e}}\) enfant de droite de \(\frac{y}{1+y}\) est \(x = \frac{y}{1+y}+k\). L’enfant de droite de \(y\) est \(y + 1\) et le \(k^{\textrm{e}}\) enfant de gauche de \(y+1\) est \(z = \frac{y + 1}{1 + k(y+1)}\). On remarque que c’est cohérant avec le scénario précédent lorsque \(k = 0\). Une petite observation importante nous permettra d’exprimer \(z\) en fonction de \(x\). Puisque \(\frac{y}{1+y}\) étant un enfant de gauche, c’est une fraction strictement comprise entre \(0\) et \(1\) et donc dans \(x = \frac{y}{1 + y} + k\), \(k\) est la partie entière de \(x\), qu’on peut noter \(\left[x\right]\) et \(\frac{y}{1+y}\) est la partie fractionnaire de \(x\), qu’on peut noter \(\left\{x\right\}\). On trouve enfin \begin{align*}z &=\frac{y+1}{1+k(y+1)} \\ \\ &= \frac{\frac{y+1}{y+1}}{\frac{1}{y+1} + \frac{k(y+1)}{y+1}} \\ \\ &= \frac{1}{\frac{1}{y+1}+k} \\ \\ &= \frac{1}{\frac{1}{y+1}+k+1-1} \\ \\ &=\frac{1}{\frac{1}{y+1}+k+1-\frac{y+1}{y+1}} \\ \\ &=\frac{1}{k + 1-\frac{y}{y+1}}\\ \\ &=\frac{1}{\left[x\right] + 1-\left\{x\right\}}\end{align*}En d’autres mots, avec \(x_{1} = 1\), on génère la suite grâce à \[x_{n+1} = \frac{1}{\left[x_{n}\right]+1-\left\{x_{n}\right\}}\]
En terminant, il est évident que le dénominateur de l’enfant de gauche est égal au numérateur de l’enfant de droite d’un même parent (c’est \(a + b\)). Il n’est donc pas surprenant que le dénominateur de certaines fractions de la liste soit égal au numérateur de la fraction suivante. En réalité cette relation s’applique à toutes les fractions de la liste, une observation que les élèves ne manqueront pas de faire.\[\left\{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \ \dots \right\}\]Le dénominateur de \(\frac{y}{1+y}+k = \frac{y+k(1+y)}{1+y}\) est égal au numérateur de \(\frac{y+1}{1 + k(y+1)}\). Si on dresse la liste des numérateurs seuls, on obtient \[\left\{1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, \, \dots \ \right\}\]Cette suite porte le nom de suite diatomique de Stern. La suite est habituellement définie par récursion. Appelons la suite \(s\). Il est d’usage de faire précéder le premier \(1\) par un \(0\) et de faire commencer la suite au \(0^{\textrm{e}}\) terme.\[\left\{0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, \, \dots \ \right\}\]La suite se définit alors simplement : \begin{align*}s(0)=0&, \ \ s(1) = 1 \\ \\ s(2n+1) &= s(n)+s(n+1) \\ \\ s(2n)&=s(n)\end{align*}
La suite regorge de propriétés à faire découvrir à des élèves attentifs. En voici quelques unes présentées sans démonstration. Les nombres coincés entre les \(1\) de la suite forment des palindromes.\[\left\{1, 1, \textcolor{Red}{2}, 1, \textcolor{Red}{3, 2, 3}, 1, \textcolor{Red}{4, 3, 5, 2, 5, 3, 4},1, \textcolor{Red}{5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5}, 1, \textcolor{Red}{6, 5, 9,\, \dots}\ \right\}\]La longueur de ces palindromes est toujours \(1\) de moins qu’une puissance de \(2\). \[\left\{1,\underset{0}{\underbrace{ \ }}1, \underset{1}{\underbrace{\textcolor{Red}{2}}}, 1, \underset{3}{\underbrace{\textcolor{Red}{3, 2, 3}}}, 1, \underset{7}{\underbrace{\textcolor{Red}{4, 3, 5, 2, 5, 3, 4}}},1, \underset{15}{\underbrace{\textcolor{Red}{5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5}}}, 1,\textcolor{Red}{6, 5, 9,\, \dots}\ \right\}\]La somme des chiffres des palindromes sont \(1\) de moins que les puissances de \(3\).\[\left\{1,\underset{0}{\underbrace{ \ }}1, \underset{2}{\underbrace{\textcolor{Red}{2}}}, 1, \underset{8}{\underbrace{\textcolor{Red}{3, 2, 3}}}, 1, \underset{26}{\underbrace{\textcolor{Red}{4, 3, 5, 2, 5, 3, 4}}},1, \underset{80}{\underbrace{\textcolor{Red}{5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5}}}, 1,\textcolor{Red}{6, 5, 9,\, \dots}\ \right\}\]Les plus grands nombres de chaque palindrome forment la suite de Fibonacci (après les \(1\) initiaux).\[\left\{1, 1, \textcolor[RGB]{0,0,255}{2}, 1, \textcolor[RGB]{0,0,255}{3}, \textcolor{Red}{2}, \textcolor[RGB]{0,0,255}{3}, 1, \textcolor{Red}{4, 3},\textcolor[RGB]{0,0,255}{5}, \textcolor{Red}{2}, \textcolor[RGB]{0,0,255}{5}, \textcolor{Red}{3, 4},1, \textcolor{Red}{5, 4, 7, 3}, \textcolor[RGB]{0,0,255}{8},\textcolor{Red}{5, 7, 2, 7, 5},\textcolor[RGB]{0,0,255}{8}, \textcolor{Red}{3, 7, 4, 5}, 1, \textcolor{Red}{6, 5, 9,\, \dots}\ \right\}\]On considère les termes aux positions impaires de la suite : ils sont la somme de leur deux voisins (sauf le tout premier terme de la suite qui n’a pas de voisin à gauche).\[\left\{1, 1, \textcolor{Red}{2}, 1, \textcolor{Red}{3}, 2, \textcolor{Red}{3}, 1, \textcolor{Red}{4}, 3, \textcolor{Red}{5}, 2, \textcolor{Red}{5}, 3, \textcolor{Red}{4}, 1, \textcolor{Red}{5}, 4, \textcolor{Red}{7}, 3, \textcolor{Red}{8}, 5, \textcolor{Red}{7}, 2, \textcolor{Red}{7}, 5, \textcolor{Red}{8}, 3, \textcolor{Red}{7}, 4, \textcolor{Red}{5}, 1, \textcolor{Red}{6}, 5, \textcolor{Red}{9}, \, \dots \ \right\}\]Et si on élimine chacun de ces nombres aux positions impaires,\[\left\{\cancel{1}, 1, \cancel{\textcolor{Red}{2}}, 1, \cancel{\textcolor{Red}{3}}, 2, \cancel{\textcolor{Red}{3}}, 1, \cancel{\textcolor{Red}{4}}, 3, \cancel{\textcolor{Red}{5}}, 2, \cancel{\textcolor{Red}{5}}, 3, \cancel{\textcolor{Red}{4}}, 1, \cancel{\textcolor{Red}{5}}, 4, \cancel{\textcolor{Red}{7}}, 3, \cancel{\textcolor{Red}{8}}, 5, \cancel{\textcolor{Red}{7}}, 2, \cancel{\textcolor{Red}{7}}, 5, \cancel{\textcolor{Red}{8}}, 3, \cancel{\textcolor{Red}{7}}, 4, \cancel{\textcolor{Red}{5}}, 1, \cancel{\textcolor{Red}{6}}, 5, \cancel{\textcolor{Red}{9}}, \, \dots \ \right\}\]on obtient\[\left\{1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5,\, \dots \ \right\}\]la suite elle-même, la suite diatomique de Stern ! (Surprise assurée de la part des élèves.)
En terminant, la suite peut exprimer le nombre de façons différentes d’écrire un nombre en base \(2\) si on autorise aussi le chiffre \(2\) dans son écriture. On parle alors d’écriture hyperbinaire d’un nombre.\[\left\{1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, \, \dots \ \right\}\]Le nombre de façons différentes d’écrire \(n\) en hyperbinaire est \(s(n+1)\). Par exemple, il y a \(5\) façon d’écrire le nombre \(10\) en base \(2\) en autorisant l’utilisation du chiffre \(2\) puisque que \[s(10+1)=s(11) = 5\]Ces façons sont \begin{align*}10 &= 1010_{2} \\ \\ &=1002_{2} \\ \\ &=210_{2} \\ \\ &=202_{2} \\ \\ &=122_{2}\end{align*}Une interprétation simple et concrète de l’écriture des nombres en hyperbinaire est celle-ci : cela correspond au nombre de façons de poser sur une balance une masse de \(n\) kg en ayant à notre disposition deux poids de \(1\) kg, deux poids de \(2\) kg, deux poids de \(4\) kg, deux poids de \(8\) kg, etc. Par exemple, puisque \(s(9+1) = s(10) = 3\), il y a donc \(3\) façons de peser une masse de \(9\) kg en utilisant ces poids : \begin{align*}9&=1\times 8 + 1 \times 1 \\ \\ &=2\times 4 + 1\times 1 \\ \\ &=1 \times 4 + 2 \times 2 + 1\times 1\end{align*}
Soit \(m\) la masse à poser sur la balance. Si \(m\) est pair, donc \(m = 2n\) pour un certain \(n\), il faut utiliser soit les deux poids de \(1\) kg, soit aucun poids de \(1\) kg. Si on utilise deux poids de \(1\) kg, il faut balancer la masse restante de \(m-2 = 2n-2\) avec l’ensemble des poids pairs, c’est-à-dire deux poids de \(2\) kg, deux poids de \(4\) kg, deux poids de \(8\) kg, etc. Cela revient à peser une masse de \(\frac{m-2}{2} = \frac{2n-2}{2}=n-1\) avec l’ensemble de poids habituel. Dans le cas où aucune masse de \(1\) kg est utilisée, cela revient également n’utiliser que les poids pairs : deux poids de \(2\) kg, deux poids de \(4\) kg, deux poids de \(8\) kg, etc. Cela revient à peser une masse de \(\frac{m}{2} = \frac{2n}{2}=n\) avec l’ensemble de poids habituel. Ainsi, on trouve que pour peser une masse de \(m=2n\) kg, on a \begin{align*}s(2n+1) &= s(n-1+1)+s(n+1)\\ \\ &=s(n) + s(n+1)\end{align*}ce qui correspond à la première relation définissant la suite.
À l’inverse, si la masse à peser est \(m\), et que \(m\) est impair, donc \(m=2n-1\) pour un certain \(n\), il faut nécessairement utiliser un seul poids de \(1\) kg. Cela revient donc à écarter l’autre poids de \(1\) kg et essayer de balancer la masse restante de \(m-1 = 2n-1-1 = 2n-2\) avec seulement des poids pairs, c’est-à-dire deux poids de \(2\) kg, deux poids de \(4\) kg, deux poids de \(8\) kg, etc. Bien sûr, cela revient à peser une masse de \(\frac{m-1}{2} = \frac{2n-2}{2}=n-1\) avec l’ensemble de poids habituel. Ainsi, on trouve \begin{align*}s(2n-1+1) &= s(n-1+1) \\ \\ s(2n)&=s(n)\end{align*}soit la deuxième relation vue ci-haut définissant la suite.
Référence :
Aigner, Martin et Günter M. Ziegler, Proofs from THE BOOK, 4\(^{\textrm{e}}\) édition, Springer, 2009
Calkin, Neil et Herbert S. Wilf, Recounting the Rationals, American Mathematical Monthly 107, p360-p363, 2000
Tanton, James, Mathematics Galore ! : The First Five Years of the St. Mark’s Institute of Mathematics, MAA, 2012
Enfin, deux séries alternées.
