L'arbre de Stern-Brocot : énumération des rationnels

Le numérateur et le dénominateur de la racine $1/1$ sont clairement premiers entre eux.

Prenons $i/j$ un noeud quelconque de l’arbre, c’est-à-dire $(i, j)$ dans $\mathbf N\times\mathbf N^*$. On a alors :

Ainsi, si $i$ et $j$ premiers entre eux, le fils gauche $\frac{i}{i + j}$ du noeud $\frac ij$ la vérifie, de même que le fils droit $\frac{i + j}{j}$.

Par induction structurelle sur le niveau d’exploration de l’arbre, on en déduit le lemme.

Prenons deux noeuds $a/b$ et $c/d$ ayant tous deux pour fils gauche $p/q$.

Par définition :

$\frac pq = \frac{a}{a+b} = \frac{c}{c+d}.$

Donc, on a successivement :

• $a(c+d) = c(a+b)$
• $ac + ad = ac + cb$
• $ad = cb$
• $a/b = c/d$ car $b, d \neq 0$

Mais ces deux fractions sont irréductibles donc $a = c$ et $b = d$.

On conclut de même dans le cas où les fils droits sont identiques.

Prenons $N$ un noeud de l’arbre.

Le premier fils gauche de $N$ est son fils gauche $\frac{N}{1 + N} = \frac{N}{1 + 1 \times N}$. Donc on a le résultat pour $k = 1$.

Prenons $k \in \mathbf N^*$ tel que le noeud provenant d’une suite de $k$ fils gauches du noeud $N$ soit $\frac{N}{1 + kN}$.

Alors le fils gauche de ce noeud est :

Par principe de récurrence, le lemme est vérifié.

Tout d’abord, $(v_{n})$ est bien définie sur $\mathbf N$ et à valeurs dans $\mathbf Q^{+}$, par définition de l’arbre. Prouvons maintenant qu’elle est surjective puis injective.

• La surjectivité

La surjectivité est équivalente au fait que tout nombre rationnel strictement positif apparaît dans l’arbre. Supposons que ce ne soit pas le cas et, parmi les rationnels strictement positifs n’apparaissant pas dans l’arbre, prenons-en un $\frac pq$ de dénominateur positif minimal.

Comme $1$ est dans l’arbre, $p \neq q$.

Si $p \lt q$, $\frac{p}{q - p}$ a un dénominateur plus petit et positif donc apparaît dans l’arbre. Mais le fils gauche de $\frac{p}{q - p}$ est $\frac{p}{q - p + p} = \frac pq$, ce qui est absurde puisque $\frac pq$ est absent de l’arbre par hypothèse.

On conclut de même dans le cas $p > q$.

• L’injectivité

L’injectivité est équivalente au fait qu’aucun nombre rationnel apparaît deux fois dans l’arbre. Par l’absurde, prenons $\frac pq$ apparaissant plusieurs fois dans l’arbre et de dénominateur positif minimal.

Il a été vu plus haut que $1$ n’était présent qu’à la racine, donc $p \neq q$. Si $p \lt q$, on a :

Cet arbre sous-entend que $\frac{p}{q-p}$ est le seul père possible pour $\frac pq$. Heureusement, c’est le cas, puisque $\frac{p}{q-p}$ est un père valable pour $\frac pq$ et deux noeuds ayant des fils gauches (ou droits) identiques ont les mêmes numérateur et dénominateur.

Donc, puisque $\frac{q}{q - p} \neq \frac pq$, $\frac pq$ apparaît au moins une fois comme enfant d’un autre noeud, c’est-à-dire que $\frac{p}{q - p}$ apparaît plusieurs fois dans l’arbre, ce qui contredit la minimalité du dénominateur.

On conclut de même dans le cas $p > q$.

On en conclut que $(v_{n})$ est bijective puis que $\mathbf Q^{+}$ est dénombrable et que $\mathbf Q$ l’est.

En considérant que la racine est au niveau $0$, on obtient facilement que le $n$^ème niveau de l’arbre comporte $2^n$ éléments et que l’élément le plus à gauche a pour numéro $2^n$.

Prenons alors $m \geq 1$ et notons $N$ le noeud numéroté par $m$ dans notre parcours en largeur. $n$ désignera le niveau auquel se positionne $N$.

Il y a $m - 2^n$ noeuds à gauche et sur le même niveau que $N$ et $2^{n+1} - m$ à sa droite. Chaque noeud à sa gauche ayant deux fils, le fils gauche de $N$ aura pour numéro $m + 2(m - 2^n) + (2^{n+1} - m) = 2m$. Le numéro du fils droit est alors $2m+1$.

On en conclut la proposition.

Tout d’abord $v_{0} = 0 = \frac 01 = \frac{s_{0}}{s_{1}}$ et $v_{1} = 1 = \frac 11 = \frac{s_{1}}{s_{2}}$. Le résultat est donc vérifié pour $n = 0$ et $n = 1$.

Prenons $m$ dans $\mathbf N$ tel que $v_{m} = \frac{s_{m}}{s_{m+1}}$.

Alors, pour $n = 2m$, $v_{n}$ est le fils gauche de $v_{m}$ et on a :

$v_{n} = \dfrac{s_{m}}{s_{m} + s_{m+1}} = \dfrac{s_{2m}}{s_{2m+1}} = \dfrac{s_{n}}{s_{n+1}}.$

De même, si $v_{n}$ est le fils droit de $v_{m}$, $n = 2m+1$ et on a :

$v_{n} = \dfrac{s_{m} + s_{m+1}}{s_{m+1}} = \dfrac{s_{2m+1}}{s_{2(m+1)}} = \dfrac{s_{n}}{s_{n+1}}.$

Par induction structurelle, on en conclut le théorème.

On a bien : $f(v_0) = f(0) = 1 = v_1$ et $f(v_1) = f(1) = \frac 12 = v_2$.

• Prenons, pour $m \geq 1$, $n = 2m$ pair.

Alors $s_n < s_{n+1}$ car $s_n = s_{2m} = s_m$ et $s_{n+1} = s_m + s_{m+1}$. D’où

Donc $v_{n+1} = f(v_n)$.

• Prenons, pour $m \geq 1$, $n = 2m+1$ impair et supposons que $v_n$ ne soit pas au bord droit de l’arbre.

Alors $v_n$ et $v_{n+1}$ ont un ancêtre commun, noté $v_p$, $k+1$ niveaux au-dessus d’eux, $k \geq 1$, et $v_n$ provient d’une suite de $k$ fils droits du fils gauche de $v_p$ tandis que $v_{n+1}$ d’une suite de $k$ fils gauches du fils droit de $v_p$.

Mais le fils droit d’un noeud $N$ est $1 + N$ et son fils gauche est $\frac{N}{1+N}$.

Donc $v_n = k + \frac{v_p}{1+v_p}$ et $v_{n+1} = \frac{1 + v_p}{1 + k(v_p+1)}$. Mais :

Donc $v_{n+1} = f(v_n)$.

• Prenons, pour $m \geq 1$, $n = 2m+1$ impair et supposons que $v_n$ soit au bord droit de l’arbre.

Notons $k \geq 1$ tel que $v_n$ provienne d’une suite de $k$ fils droits en partant de la racine. Alors $v_{n+1}$ provient d’une suite de $k+1$ fils gauches en partant de la racine.

On a alors $v_n = \lfloor v_n \rfloor = k+1$. Mais $v_{n+1} = \frac{1}{1+(k+1)}$.

Donc $v_{n+1} = f(v_n)$.

En somme, le théorème est vérifié.