Théorème de Zeckendorf

Représentation de Zeckendorf des 89 premiers entiers. Les largeurs des rectangles sont des nombres de Fibonacci Modèle:Mvar, et les hauteurs correspondantes ont pour valeur Modèle:Math. Les rectangles de même couleur ont mêmes dimensions.

Le théorème de Zeckendorf, dénommé ainsi en référence au mathématicien belge Édouard Zeckendorf, est un théorème de théorie additive des nombres qui garantit que tout entier naturel Modèle:Mvar peut être représenté, de manière unique, comme somme de nombres de Fibonacci distincts et non consécutifs. Cette représentation est appelée la représentation de Zeckendorf de Modèle:Mvar.

Énoncé et exemple

Modèle:Théorème Par exemple, Modèle:Math est représenté par la somme vide. La représentation de Zeckendorf du nombre Modèle:Math est

$100=89+8+3=F_{11}+F_6+F_4$.

Le nombre Modèle:Math possède d'autres représentations comme somme de nombres de Fibonacci. Ainsi :

$100=89+8+2+1$

$100=89+5+3+2+1$

$100=55+34+8+3$

$100=55+34+8+2+1$

$100=55+34+5+3+2+1$

$100=55+21+13+8+3$

mais ces représentations contiennent des nombres de Fibonacci consécutifs. À toute représentation d'un entier Modèle:Mvar, on associe un mot binaire, dont la Modèle:Mvar-ième lettre en partant de la droite est Modèle:Math si $F_{n+1}$ figure dans la représentation de Modèle:Mvar et Modèle:Math sinon. Ainsi, aux représentations de Modèle:Math ci-dessus sont associés les mots :

$F_{11}+F_6+F_4=1000010100_{Zeck}$

$1000010011$

$1000001111$

$110010100$

$110010011$

$110001111$

$101110100$.

Les entiers de 0 à 4 ont pour représentations de Zeckendorf : $0=0_{\text{Zeck}},1=F_2=1_{\text{Zeck}},2=F_3=10_{\text{Zeck}},3=F_4=100_{\text{Zeck}},4=F_4+F_2=101_{\text{Zeck}}$.

Les mots binaires de Zeckendorf associés aux entiers successifs, lus en base 10 : 0, 1, 10, 100, 101, 1000, 1001, etc forment la Modèle:OEIS.

L'ensemble de ces mots binaires forme un langage rationnel : ce sont le mot vide et les mots commençant par Modèle:Math et ne contenant pas deux Modèle:Math consécutifs. Une expression rationnelle de ce langage est

$0+1(0+01{)}^{*}$.

Le codage de Fibonacci d'un entier est, par définition, le mot binaire associé à sa représentation, retourné et suivi d'un symbole Modèle:Math. Ainsi, le codage de Fibonacci du nombre Modèle:Math est Modèle:Math.

Note historique

Zeckendorf a publié sa démonstration du théorème en 1972, alors que l'énoncé était connu, sous le nom de « théorème de Zeckendorf », depuis longtemps. Ce paradoxe est expliqué dans l'introduction de l'article de Zeckendorf : un autre mathématicien, Modèle:Lien, a rédigé la preuve du théorème (et d'autres résultats) à la suite d'un exposé de Zeckendorf, et l'a publié en 1952, tout en en attribuant la paternité à Zeckendorf. D'après Clark Kimberling, c'est un article de David E. Daykin, publié dans un journal prestigieux, qui a contribué à faire connaître le résultat et son auteur.

Démonstration

La démonstration du théorème est en deux parties :

1. Existence : L'existence de la représentation se démontre par l'emploi de l'algorithme glouton ou par récurrence sur Modèle:Mvar, ce qui revient strictement au même. Modèle:Démonstration

2. Unicité : Pour cette partie, on utilise le lemme suivant : Modèle:Théorème Modèle:Démonstration Modèle:Démonstration

Représentation des premiers entiers

Dans la table, Modèle:Math dénote la représentation de Modèle:Mvar sous forme de mot binaire.

Modèle:Mvar	Modèle:Math
0	0
1	1
2	10
3	100
4	101
5	1000
6	1001
7	1010
8	10000
9	10001
10	10010
11	10100

L'alternance des 0 et 1 dans chacune des colonnes correspond à l'absence ou la présence d'un rectangle dans la figure en tête de la page. La suite des derniers chiffres est

$010010100100\cdots$

C'est le début du mot de Fibonacci. En effet, le N-ième symbole du mot de Fibonacci est 0 ou 1 selon que $N$ est « Fibonacci pair » (Modèle:Math se termine par 0) ou « Fibonacci impair ».

Addition et multiplication en numération de Zeckendorf

Christiane Frougny, de l’Institut de recherche en informatique fondamentale, à Paris, a découvert en 1991 un algorithme permettant d’additionner deux nombres en numération de Zeckendorf sans passer par une autre représentationModèle:,Modèle:,.

De même, Tomasz Idziaszek a proposé un algorithme similaire pour la multiplicationModèle:,.

Variations

Représentation par des nombres de Fibonacci d'indices négatifs

La suite des nombres de Fibonacci peut être étendue aux indices négatifs, puisque la relation

$F_n=F_{n-1}+F_{n-2}$

permet de calculer $F_{n-2}$ à partir de Modèle:Mvar et de $F_{n-1}$. On a (voir la section correspondante de l'article sur les nombres de Fibonacci) :

$F_{-n}=(-1{)}^{n+1}{F}_n.$

La suite complète est $\dots ,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,\dots$ Donald Knuth a remarqué que tout entier relatif est somme de nombres de Fibonacci d'indices strictement négatifs qu'il appelle « Negafibonacci », la représentation étant unique si deux nombres utilisés ne sont pas consécutifs. Par exemple :

• $-11=F_{-4}+F_{-6}=(-3)+(-8)$ ;
• $12=F_{-2}+F_{-7}=(-1)+13$ ;
• $24=F_{-1}+F_{-4}+F_{-6}+F_{-9}=1+(-3)+(-8)+34$ ;
• $-43=F_{-2}+F_{-7}+F_{-10}=(-1)+13+(-55).$

Comme plus haut, on associe à la représentation d'un entier Modèle:Mvar un mot binaire, dont la Modèle:Mvar-ième lettre est Modèle:Math si Modèle:Mvar figure dans la représentation de Modèle:Mvar et Modèle:Math sinon. Ainsi, Modèle:Math est représenté par le mot Modèle:Math. On observe que l'entier Modèle:Mvar est positif si et seulement si la longueur du mot associé est impaire.

Multiplication de Fibonacci

Donald Knuth considère une opération de multiplication $a\circ b$ d'entiers naturels $a$ et $b$ définie comme suit : étant donné les représentations $a=\sum _{i=0}^k{F}_{c_i}(c_i\ge 2)$ et $b=\sum _{j=0}^l{F}_{d_j}(d_j\ge 2)$ le produit de Fibonacci est l'entier $a\circ b=\sum _{i=0}^k\sum _{j=0}^l{F}_{c_i+d_j}.$

Par exemple, comme Modèle:Math et Modèle:Math, on a $2\circ 4=F_{3+4}+F_{3+2}=13+5=18$.

Knuth a prouvé le fait surprenant que cette opération est associative.

Autres suites

Zeckendorf prouve l'existence et l'unicité, sous condition, pour la représentation par les nombres de Lucas.

Knuth mentionne que le théorème de Zeckendorf reste vrai pour les suites de k-bonacci, sous réserve que l'on n'utilise pas Modèle:Mvar nombres consécutifs d'une telle suite.

Aviezri Fraenkel a donné un énoncé général qui étend les théorèmes précédents : Soit $1=u_0<u_1<u_2<\cdots$ une suite d'entiers. Tout entier naturel Modèle:Mvar a exactement une représentation de la forme

$N=d_k{u}_k+d_{k-1}{u}_{k-1}+\cdots +d_1{u}_1+d_0{u}_0,$

où $d_k,\dots ,d_0$ sont des entiers naturels, pourvu que

$d_i{u}_i+d_{i-1}{u}_{i-1}+\cdots +d_0{u}_0<u_{i+1}$

pour $i\ge 0.$

Système d'Ostrowski

Modèle:Article lié Tout nombre irrationnel Modèle:Mvar admet un développement en fraction continue $\alpha =[a_0,a_1,a_2,\dots ]$. Si l'on pose $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, $q_{-1}=0$ et $p_n=a_n{p}_{n-1}+p_{n-2}$, $q_n=a_n{q}_{n-1}+q_{n-2}$, on a $p_n/q_n=[a_0,\dots ,a_n]$. La suite $(q_n)$ forme une base pour un système de numération : Modèle:Théorème Pour le nombre d'or, les Modèle:Mvar valent tous 1, les Modèle:Mvar sont les nombres de Fibonacci et les trois conditions signifient que les termes de la somme sont distincts et non consécutifs.

Voir aussi

Articles connexes

• Codage de Fibonacci
• Système de numération

Liens externes

• Modèle:MathWorld
• Modèle:MathWorld
• Une réciproque du théorème de Zeckendorf : Zeckendorf's theorem sur le site cut-the-knot
• Modèle:EncycloMath
• La Modèle:OEIS décrit la multiplication de Fibonacci
• Un tour de magie mathématique basé sur le théorème de Zeckendorf, sur Blogdemaths