0.1.2 La numération de Zeckendorf

Posons $f_0=1, f_1=2$ et, pour $n\geq 0$, $f_{n+2}=f_{n+1}+f_n$ (^0.2). Voici les premiers éléments de cette suite.

$$% latex2html id marker 2396\begin{array}{c\vert c\vert c\v... ...n&0&1&2&3&4&5&6&7\\ \hline f_n&1&2&3&5&8&13&21&34 \end{array}$$

On peut vérifier que tout entier positif $n$ s'écrit, de manière unique, sous la forme

$$n=\sum_{i\in I}f_i$$

où dans $I$, il n'y a pas d'éléments consécutifs. Une façon simple de s'en convaincre est de construire la décomposition de $n$ par récurrence: $n$ est encadré par deux éléments consécutifs de la suite

$$f_{r-1}\leq n<f_r.$$

On place $r-1$ dans $I$ puis on recommence en substituant $n-f_{r-1}$ à $n$. Il faut vérifier qu'à la fin, il n'y aura pas d'éléments consécutifs dans $I$ ainsi que l'unicité de la décompostion (^0.3). Voici ce que cela donne pour $27$:

$$% latex2html id marker 2424\begin{array}{c\vert c\vert c} ... ... \hline 27&6&21\\ \hline 6&3&5\\ \hline 1&0&1 \end{array}$$

On peut donc représenter $27$ par $1001001$, les $1$ occupant les positions dont les rangs comptés de droite à gauche et à partir de zéro, sont les éléments de $I=\{0,3,6\}$. En codant de la même façon tous les entiers positifs et en représentant zéro par 0, on obtient un système de numération, le système de Zeckendorf. Le langage de numération associé est écrit sur l'alphabet $\{0,1\}$. Il est régulier: c'est l'intersection du langage contenant 0 et les mots commençants par $1$ et du langage formé des mots ne contenant pas le facteur $11$, qui sont tous les deux réguliers.