Alphabet fini

L'algorithme glouton donne une représentation de chaque entier. Elle fait apparaître des coefficients $a_i$ dont l'ensemble, lorsque $n$ décrit ${\rm I\!N}$, représente les chiffres de la numération.

Proposition 0.1.1   L'alphabet des chiffres associé à une suite strictement croissante d'entiers $U_n$, avec $U_0=1$, est fini si et seulement si le quotient $\frac{U_r}{U_{r-1}}$ est borné. Lorsque l'alphabet est fini, ses éléments sont bornés par $\lfloor \sup\{ \frac{U_r}{U_{r-1}}, r=1,2,\ldots\}\rfloor$

Preuve. Supposons que l'alphabet des chiffres soit fini. Le chiffre $a$ le plus à gauche de la représentation de $U_r-1$ est le quotient entier de ce dernier par $U_{r-1}$. En notant $b$ le reste de cette division, on voit que

$$\frac{U_r}{U_{r-1}}=a+\frac{b+1}{U_{r-1}}\leq a+1$$

est majoré par le plus grand des chiffres. Inversement, supposons que le quotient $\frac{U_r}{U_{r-1}}$ soit borné et soit un chiffre non nul $a$. Il existe un indice $r$, un entier positif $n<U_r$ et un entier $b$ vérifiant (). Par conséquent,

$$a=\frac{n}{U_{r-1}}-\frac{b}{U_{r-1}}< \frac{U_r}{U_{r-1}}$$

est majoré par la meilleure borne supérieure des $\frac{U_r}{U_{r-1}}$.$\qed$

Pour une numération classique, de base $k$, la suite ${\bf U}$ est donnée par $U_n=k^n$. Le quotient $\frac{U_r}{U_{r-1}}=k$ est donc constant. Les chiffres sont compris entre 0 et $k-1$. Pour le système de Zekendorf, on peut vérifier que

$$f_r=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{r+2}-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{r+2}$$

Par conséquent

$$\lim_r\frac{f_r}{f_{r-1}}=\frac{1+\sqrt{5y}}{2}<2.$$

On confirme ainsi qu'il n'y a que deux chiffres dans ce système.