Théorème de Zeckendorf

Représentation de Zeckendorf des 89 premiers entiers. Les largeurs des rectangles sont des nombres de Fibonacci

F i

, et les hauteurs correspondantes ont pour valeur

F i -1

.
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 $N$ peut être décomposé, de manière unique, comme somme de nombres de Fibonacci distincts et non consécutifs. Cette décomposition est appelée la représentation de Zeckendorf de $N$ .

Énoncé et exemples

Théorème de Zeckendorf^[1] — Pour tout entier naturel $N$ , il existe une unique suite d’entiers $c 0, ... , c k$ , avec $c_{0}\geqslant 2$ et $c i +1 > c i + 1$ , tels que

N=\sum _{i=0}^{k}F_{c_{i}}

,

où $F n$ est le nombre de Fibonacci d'indice $n$ .

Les nombres de Fibonacci de rang supérieur ou égal à deux utilisables dans une décomposition de Zeckendorf forment la suite suivante^[2] :

$F 2$	$F 3$	$F 4$	$F 5$	$F 6$	$F 7$	$F 8$	$F 9$	$F 10$	$F 11$	$F 12$	$F 13$	$F 14$	$F 15$	...	$F n$
1	2	3	5	8	13	21	34	55	89	144	233	377	610	...	$F n - 1 + F n - 2$

Exemples :

les entiers de 0 à 4 ont pour décompositions de Zeckendorf^[3] : $0=0;1=F_{2};2=F_{3};3=F_{4};4=F_{4}+F_{2}$ ;
la décomposition de Zeckendorf du nombre cent est $100=89+8+3=F_{11}+F_{6}+F_{4}$ .

L'exemple du nombre cent permet d'illustrer l'importance, pour garantir l'unicité de la représentation, de la contrainte imposant de ne pas utiliser de nombres de Fibonacci consécutifs. Le nombre cent possède en effet d'autres décompositions comme somme de nombres de Fibonacci :

100=89+8+2+1=F_{11}+F_{6}+F_{3}+F_{2}

100=89+5+3+2+1=F_{11}+F_{5}+F_{4}+F_{3}+F_{2}

100=55+34+8+3=F_{10}+F_{9}+F_{6}+F_{4}

100=55+34+8+2+1=F_{10}+F_{9}+F_{6}+F_{3}+F_{2}

100=55+34+5+3+2+1=F_{10}+F_{9}+F_{5}+F_{4}+F_{3}+F_{2}

100=55+21+13+8+3=F_{10}+F_{8}+F_{7}+F_{6}+F_{2}

Mais ces décompositions contiennent toutes des nombres de Fibonacci consécutifs.

Démonstration

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

1. Existence : L'existence de la représentation se démontre par l'emploi de l'algorithme glouton^[4] ou par récurrence sur $N$ , ce qui revient au même.

Deux démonstrations de l'existence

Première démonstration

On raisonne par récurrence forte sur l'entier naturel

N

. Si

N

est nul, il est représenté par la somme vide. Sinon, soit

F k

, avec

k\geqslant 2

, le plus grand nombre de Fibonacci inférieur ou égal à

N

et soit

M=N-F_{k}<N

. Par hypothèse de récurrence forte,

M

possède une représentation. Alors, pour tout nombre

F_{\ell }

de cette représentation,

F_{k}+F_{\ell }\leqslant F_{k}+M=N<F_{k+1}=F_{k}+F_{k-1}

donc

F_{\ell }<F_{k-1}

. La représentation de

M

, augmentée de

F k

, est donc bien une représentation de

N

.

Seconde démonstration

On raisonne par récurrence simple sur l'entier

N

considéré. L'existence est facilement vérifiable pour les petites valeurs de

N

. Supposons qu'elle soit vraie pour un entier

N

donné et décomposons cet entier en rangeant les nombres de Fibonacci par ordre croissant. Plusieurs cas sont à considérer :

Si $N=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}$ avec $4\leqslant i_{1}$ et $\forall j,i_{j+1}\geqslant i_{j}+2$ , alors :
$N+1=F_{2}+F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}$
Si $N=F_{3}+F_{5}+\cdots +F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ avec $i_{r}\geqslant 2r+2$ et $\forall j,i_{j+1}\geqslant i_{j}+2$ (et éventuellement $i_{s}=2r-1$ auquel cas les termes $F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ n'existent pas). Alors :
$N+1=F_{2r}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$
Si $N=F_{2}+F_{4}+\cdots +F_{2r-2}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ avec $i_{r}\geqslant 2r+1$ et $\forall j,i_{j+1}\geqslant i_{j}+2$ (et éventuellement $i_{s}=2r-2$ auquel cas les termes $F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ n'existent pas). Alors :
$N+1=F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$

Ainsi,

N+1

admet aussi une décomposition.

2. Unicité : Pour cette partie, on utilise le lemme suivant :

Lemme — La somme de tout ensemble non vide de nombres de Fibonacci distincts et non consécutifs, dont le plus grand élément est $F j$ , est strictement inférieure à $F j +1$ .

Deux démonstrations du lemme

Première démonstration

On raisonne par récurrence simple sur le nombre d'éléments d'un tel ensemble

S

. L'initialisation est immédiate. Pour l'hérédité, si

S

a plus d'un élément, enlevons

F j

. Par hypothèse de récurrence, la somme des éléments restants est strictement inférieure à

F j -1

, donc la somme totale est strictement inférieure à

F j -1 + F j = F j +1

.

Seconde démonstration

Si

n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}

avec

\forall j,i_{j+1}\geqslant i_{j}+2

. Alors :

si $i s$ est pair :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leqslant F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{2}$

donc :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}<F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{2}+1=F_{i_{s}-1}$
si $i s$ est impair :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leqslant F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{3}$

donc :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}<F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{3}+1=F_{i_{s}-1}$

Donc, dans tous les cas,

F_{i_{s}}\leqslant n<F_{i_{s}}+F_{i_{s}-1}=F_{i_{s}+1}

Preuve de l'unicité

On raisonne par récurrence forte sur l'entier naturel $N$ . D'après le lemme, dans une décomposition de $N$ , le plus grand indice $k$ pour lequel $F k$ apparaît (si la décomposition est non vide, c.-à-d. si $N\neq 0$ ) est entièrement déterminé par $F_{k}\leqslant N<F_{k+1}$ . Par hypothèse de récurrence, la décomposition de $N - F k$ (donc le reste de la décomposition de $N$ ) est également unique.

Corollaires

Les démonstrations précédentes établissent aussi les corollaires suivants :

La décomposition de Zeckendorf de tout entier naturel $N$ a pour plus grand terme le plus grand nombre de Fibonacci qui est inférieur ou égal à $N$ .

Les nombres de Fibonacci sont les seuls entiers naturels dont la décomposition de Zeckendorf ne contient qu'un nombre ( $F_{1}=F_{2}$ et pour $i>1$ : $F_{i}=F_{i}$ ).

Note historique

Zeckendorf a publié sa démonstration du théorème en 1972^[1], 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, Gerrit Lekkerkerker (en), 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é^[5] en 1952, tout en en attribuant la paternité à Zeckendorf. D'après Clark Kimberling^[6], c'est un article de David E. Daykin^[7], publié dans un journal prestigieux, qui a contribué à faire connaître le résultat et son auteur.

Représentation des entiers

Numération de Zeckendorf

Le théorème de Zeckendorf signifie que tout nombre entier naturel $N$ est égal à une somme de la forme $N=\sum _{i=2}^{k}a_{i}\times F_{i}$ avec $a_{i}=0$ ou $1$ et la condition^[8] $a_{i}\times a_{i+1}=0$ , et ce d'une seule façon. Ceci définit un système de numération positionnelle à bases mixtes constituées par $F_{2}$ en position 1, $F_{3}$ en position 2, etc., et dont les chiffres sont "0" et "1". L'écriture de $N$ dans cette numération $Zeck$ est $N=(a_{k}a_{k-1}\cdots a_{3}a_{2})_{Zeck}$ ^[9]. Elle est dénommée "représentation de Zeckendorf" ou "représentation en base de nombres de Fibonacci" de $N$ .

Dans cette numération, en reprenant les exemples du début de l'article, on écrit donc : $2_{10}=F_{3}=1\times F_{3}+0\times F_{2}=10_{Zeck}$ et $4_{10}=F_{4}+F_{2}=101_{Zeck}$ , ou encore $100_{10}=F_{11}+F_{6}+F_{4}=1000010100_{Zeck}$ .

Les représentations en numération de Zeckendorf des entiers 1, 2, 3, etc. forment la suite A014417 de l'OEIS. La table suivante donne quelques éléments de cette suite, $N_{Zeck}$ étant l'écriture en numération $Zeck$ du nombre $N$ s'écrivant $N_{10}$ en base dix :


$N_{10}$	0	1	2	3	4	5	6	7	8	9	10	11	...	98	99	100
$N_{Zeck}$	0	1	10	100	101	1000	1001	1010	10000	10001	10010	10100	...	1000010001	1000010010	1000010100

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ésentation^[10]^,^[11]^,^[12].

De même, Tomasz Idziaszek a proposé un algorithme similaire pour la multiplication^[13]^,^[12].

Mots binaires

À la décomposition de Zeckendorf d'un entier $N$ , on peut associer un mot binaire^[14], dont la $n$ -ième lettre en partant de la droite est $1$ si $F_{n+1}$ figure dans la décomposition de $N$ et $0$ sinon^[15].

L'ensemble de ces mots binaires forme un langage rationnel dont les mots sont le mot vide ainsi que tous les mots qui commencent (à gauche) par $1$ et ne contiennent pas deux $1$ consécutifs^[16]. Une expression rationnelle de ce langage est : $0+1(0+01)^{*}$ .

Dans ce langage, l'alternance des 0 et 1 à la fin des mots associés aux entiers naturels successifs correspond à l'absence ou la présence d'un rectangle dans la figure en tête de la page. La fin de ces mots constitue une suite qui commence par :

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 » ( $R (N)$ se termine par 0) ou « Fibonacci impair ».

Ce langage et ses mots sont notamment utilisés en informatique pour le codage de Fibonacci : pour un entier de $N$ , ce codage est constitué du mot binaire associé à $N$ , retourné et suivi d'un chiffre $1$ . Ainsi, le codage de Fibonacci du nombre cent est $00101000011$ .

Variantes et généralisations

Le théorème et la représentation de Zeckendorf ont fait l'objet de nombreux travaux visant à en explorer les conséquences, développer des opérations arithmétiques dans ce système de numération, construire des variantes de représentation utilisant d'autres "lettres" (par exemple -1), en utilisant les nombres de Fibonacci d'indices négatifs, en imposant aux nombres de Fibonacci utilisés dans une décomposition des contraintes autres que celle d'être non consécutifs^[17], ou encore en utilisant des suites de Lucas en lieu et place de la suite de Fibonacci. Les résultats de certains de ces travaux sont présentés ci-dessous, en commençant par la réciproque du théorème de Zeckendorf.

Réciproque du théorème de Zeckendorf

À la fin des années 1950, le mathématicien D. E. Daykin a démontré que, si une suite de chiffres entiers naturels $A_{i}(i>1)$ est telle que tout nombre entier naturel $N$ non nul s'écrive de façon unique comme la somme de nombres $A_{i}$ distincts et non consécutifs, alors la suite des $A_{i}(i>1)$ est la suite des nombres de Fibonacci d'index supérieur ou égal à deux^[7]^,^[18].

Une démonstration partielle de cette réciproque est donnée ci-dessous :

Démonstration en supposant la suite

A_{i}

croissante

Supposons qu'une suite croissante $A$ d'entiers naturels $A_{i}(i>1)$ non nuls soit telle qu'elle a la propriété énoncée. Et montrons que pour tout $i$ , $A_{i}=F_{i}$ .

Remarquons d'abord qu'une décomposition de $A_{i}$ dans $A$ est $A_{i}=A_{i}$ : c'est donc l'unique décomposition de $A_{i}$ dans $A$ .

Remarquons ensuite que $A_{2}=1,A_{3}=2,A_{4}=3$ pour assurer l'existence de la décomposition des entiers un, deux et trois. Donc l'égalité $A_{i}=F_{i}$ est vérifiée pour $i=2,3$ et $4$ .

Démontrons par récurrence forte qu'elle l'est pour tout $i$ .

Montrons d'abord que tous les $A_{i}$ sont des nombres de Fibonacci. Supposons qu'il existe des $A_{i}$ qui ne sont pas des nombres de Fibonacci et considérons $A_{m}$ , le plus petit d'entre eux. Il existe donc un $F_{j}$ tel que $F_{j}<A_{m}<F_{j+1}$ . Mais alors la décomposition de Zeckendorf de $A_{m}$ a pour plus grand terme $F_{j}$ , et cette décomposition est aussi une décomposition en $A$ puisque pour $A_{i}<A_{m}$ on a : $A_{i}=F_{i}$ . $A_{m}$ aurait donc deux décompositions en $A$ : celle-ci et $A_{m}=A_{m}$ , ce qui est contradictoire. Donc tous les $A_{i}$ sont des nombres de Fibonacci.

Montrons maintenant que tout nombre de Fibonacci est dans la suite $A$ . Supposons qu'il existe des nombres de Fibonnaci $F_{i}$ qui ne sont pas dans $A$ et considérons le plus petit d'entre eux $F_{m}$ . Et soit $A_{j}$ le plus grand $A_{i}$ inférieur à $F_{m}$ : la décomposition en $A$ de $F_{m}$ aurait donc pour terme maximal $A_{p}\leqslant A_{j}$ . Or pour $i\leqslant m$ on a $A_{i}=F_{i}$ : cette décomposition en $A$ est donc aussi une décomposition de Zekendorf. Donc $F_{m}$ aurait deux décompositions de Zeckendorf : celle-ci et $F_{m}=F_{m}$ , ce qui est contradictoire. Donc tous les nombres de Fibonacci sont dans $A$ , ce qui termine la démonstration.

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 $F n$ 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 des nombres de Fibonacci d'indice strictement négatif commence comme suit :

$F -1$	$F -2$	$F -3$	$F -4$	$F -5$	$F -6$	$F -7$	$F -8$	$F -9$	$F -10$	$F -11$	$F -12$	$F -13$	$F -14$	$F -15$	...	$F -n$
$1$	$-1$	$2$	$-3$	$5$	$-8$	$13$	$-21$	$34$	$-55$	$89$	$-144$	$233$	$-377$	$610$	...	$(-1)^{n+1}F_{n}$

Au début des années 1990, le mathématicien M. W. Bunder a démontré que tout entier relatif est somme de nombres de Fibonacci d'indices strictement négatifs la représentation étant unique si deux nombres utilisés ne sont pas consécutifs^[19]^,^[20]. 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 $N$ un mot binaire, dont la $n$ -ième lettre est $1$ si $F -n$ figure dans la représentation de $N$ et $0$ sinon. Ainsi, $24$ est représenté par le mot $100101001$ . On observe que l'entier $N$ est positif si et seulement si la longueur du mot associé est impaire.

Multiplication de Fibonacci

Donald Knuth^[21] définit une opération de multiplication dite produit de Fibonacci d'entiers naturels $a$ et $b$ et notée $a\circ b$ comme suit : étant donné les représentations $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ et $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$ , leur 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 $2 = F 3$ et $4 = F 4 + F 2$ , on a $2\circ 4=F_{3+4}+F_{3+2}=13+5=18$ .

D. Knuth a prouvé 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^[1].

D. 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 $k$ nombres consécutifs d'une telle suite^[22].

Aviezri Fraenkel a donné un énoncé général qui étend les théorèmes précédents^[23] : Soit $1=u_{0}<u_{1}<u_{2}<\cdots$ une suite d'entiers. Tout entier naturel $N$ 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},\ldots ,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\geq 0.$

Système d'Ostrowski

Article connexe : Numération d'Ostrowski.

Tout nombre irrationnel $α$ admet un développement en fraction continue $\alpha =[a_{0},a_{1},a_{2},\ldots ]$ . 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},\ldots ,a_{n}]$ . La suite $(q_{n})$ forme une base pour un système de numération :

Théorème d'Ostrowski^[24] — Soit $α$ un nombre irrationnel, et soit $(q n)$ la suite des dénominateurs des convergents de la fraction continue de $α$ . Tout entier positif $N$ s'écrit de manière unique sous la forme

N=b_{k}q_{k}+\cdots +b_{0}q_{0}

où les $b i$ sont des entiers satisfaisant les trois conditions suivantes :

$0\leq b_{0}<a_{1}$ ;
$0\leq b_{i}\leq a_{i+1}$ pour $i>0$ ;
Pour $i>0$ , si $b_{i}=a_{i+1}$ , alors $b_{i-1}=0$ .

Pour le nombre d'or, les $a i$ valent tous 1, les $q n$ sont les nombres de Fibonacci et les trois conditions signifient que les termes de la somme sont distincts et non consécutifs.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Zeckendorf's theorem » (voir la liste des auteurs).

1 2 3 Édouard Zeckendorf, « Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas », Bull. Soc. Roy. Sci. Liège, vol. 41,‎ 1972, p. 179–182.
↑ La condition imposant que le rang $n$ de $F_{n}$ soit au moins égal à $2$ est très importante. En effet, dans la suite de Fibonacci, $F_{1}=F_{2}=1$ . Si on n'exclut pas $F_{1}$ , de nombreux nombres ont deux décompositions, même en respectant la contrainte de ne pas utiliser dans leur décomposition deux nombres de Fibonacci consécutifs. Par exemple : $4_{10}=F_{4}+F_{2}=F_{4}+F_{1}$ .
↑ $0$ est représenté par la somme vide.
↑ (en) Ronald Graham,Donald Knuth, Oren Patashnik, Mathématiques concrètes, Thomson publishing, 1998, p. 314 - 315
↑ (nl) Cornelis Gerrit Lekkerkerker, « Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci » [« Représentation des nombres naturels par une somme de nombres de Fibonacci »], Simon Stevin, vol. 29,‎ 1952, p. 190-195.
↑ (en) Clark Kimberling, « Edouard Zeckendorf [1901–1983] », Fibonacci Quart., vol. 36, n^o 5,‎ 1998, p. 416–418.
1 2 (en) D. E. Daykin, « Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers », Journal of the London Mathematical Society, vol. s1-35, n^o 2,‎ 1960, p. 143–160 (ISSN 1469-7750, DOI 10.1112/jlms/s1-35.2.143, lire en ligne, consulté le 14 janvier 2026)
↑ Cette condition est celle qui interdit l'usage de deux nombres de Fibonacci consécutifs.
↑ Graham, Knuth et Patashnik 1990, p. 281-283.
↑ (en) C. Frougny, « Fibonacci representations and finite automata », IEEE Transactions on Information Theory, vol. 37, n^o 2,‎ mars 1991 (lire en ligne )
↑ (en) C. Ahlbach et al., « Efficient algorithms for Zeckendorf arithmetic », Fibonacci Quarterly,‎ 2013 (arXiv 1207.4497, lire en ligne)
1 2 Jean-Paul Delahaye, « Des suites exotiques pour écrire les nombres », Pour la Science, n^o 568,‎ février 2025, p. 74
↑ (en) T. Idziaszek, « Efficient algorithm for multiplication of numbers in Zeckendorf representation », FUN 2021,‎ 2021 (lire en ligne)
↑ Ces mots sont dits "binaires" car ce langage n'utilise que deux "lettres" : 0 et 1.
↑ La dernière "lettre" en partant de la droite étant nécessairement "1".
↑ Christine Solnon, Théorie des langages (Cours), Lyon, LIRIS, 30 p. (lire en ligne [PDF]), chap. 3 (« Langages réguliers et Automates finis »), p. 15-24
↑ (en) Péter Hajnal, « A short note on Zeckendorf type numeration systems with negative digits allowed », Bulletin of the ICA, vol. 97,‎ 2023, p. 54-66 (lire en ligne [PDF])
↑ Julie Piraprez, Le théorème de Zeckendorf : généralisations et réciproques (Mémoire de fin d'études (Master)), Liège, Liège Université, 2024, 91 p. (lire en ligne [PDF])
↑ (en) Donald Knuth, « Negafibonacci Numbers and the Hyperbolic Plane », Paper presented at the annual meeting of the MAA, The Fairmont Hotel, San Jose, CA. 2008-12-11 [présentation en ligne].
↑ (en) M. W. Bunder, « Zeckendorf representations using negative Fibonacci numbers », Fibonacci Quarterly,‎ 1992 (lire en ligne [PDF])
↑ (en) Donald E. Knuth, « Fibonacci Multiplication », Applied Mathematics Letters, vol. 1, n^o 1,‎ 1988, p. 57-60 (DOI 10.1016/0893-9659(88)90176-0)
↑ Exercice 5.4.2-10 dans (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition].
↑ Aviezri S. Fraenkel, « Systems of Numeration », The American Mathematical Monthly, vol. 92, n^o 2,‎ 1985, p. 105–114 (ISSN 0002-9890, DOI 10.2307/2322638, lire en ligne, consulté le 14 janvier 2026)
↑ Ce théorème est attribué à Alexander Ostrowski (1922). Voir : (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, MR 1997038, lire en ligne), Section 3.9.

Voir aussi

Articles connexes

Liens externes

(en) Eric W. Weisstein, « Zeckendorf's Theorem », sur MathWorld
(en) Eric W. Weisstein, « Zeckendorf Representation », sur MathWorld
Une réciproque du théorème de Zeckendorf : Zeckendorf's theorem sur le site cut-the-knot
(en) « Zeckendorf representation », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
La suite A101330 de l'OEIS décrit la multiplication de Fibonacci
Un tour de magie mathématique basé sur le théorème de Zeckendorf, sur Blogdemaths

Bibliographie

(en) Graham, Knuth et Patashnik, Concrete Mathematics, Massachusetts, Addison-Wesley Publishing, 1990, 6^e éd., 640 p. (ISBN 0-201-14236-8, lire en ligne), p. 282-283.
Graham, Knuth et Patashnik, Mathématiques concrètes, Thomson publishing, 1998, p. 314-315

Portail des mathématiques

[Zeck-1] 1 2 3 Édouard Zeckendorf, « Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas », Bull. Soc. Roy. Sci. Liège, vol. 41,‎ 1972, p. 179–182.

[2] La condition imposant que le rang $n$ de $F_{n}$ soit au moins égal à $2$ est très importante. En effet, dans la suite de Fibonacci, $F_{1}=F_{2}=1$ . Si on n'exclut pas $F_{1}$ , de nombreux nombres ont deux décompositions, même en respectant la contrainte de ne pas utiliser dans leur décomposition deux nombres de Fibonacci consécutifs. Par exemple : $4_{10}=F_{4}+F_{2}=F_{4}+F_{1}$ .

[3] $0$ est représenté par la somme vide.

[4] (en) Ronald Graham,Donald Knuth, Oren Patashnik, Mathématiques concrètes, Thomson publishing, 1998, p. 314 - 315

[Lekkerkerker-5] (nl) Cornelis Gerrit Lekkerkerker, « Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci » [« Représentation des nombres naturels par une somme de nombres de Fibonacci »], Simon Stevin, vol. 29,‎ 1952, p. 190-195.

[Kimberling-6] (en) Clark Kimberling, « Edouard Zeckendorf [1901–1983] », Fibonacci Quart., vol. 36, n^o 5,‎ 1998, p. 416–418.

[:1-7] 1 2 (en) D. E. Daykin, « Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers », Journal of the London Mathematical Society, vol. s1-35, n^o 2,‎ 1960, p. 143–160 (ISSN 1469-7750, DOI 10.1112/jlms/s1-35.2.143, lire en ligne, consulté le 14 janvier 2026)

[8] Cette condition est celle qui interdit l'usage de deux nombres de Fibonacci consécutifs.

[GrahamKnuthPatashnik1990281-283-9] Graham, Knuth et Patashnik 1990, p. 281-283.

[10] (en) C. Frougny, « Fibonacci representations and finite automata », IEEE Transactions on Information Theory, vol. 37, n^o 2,‎ mars 1991 (lire en ligne )

[11] (en) C. Ahlbach et al., « Efficient algorithms for Zeckendorf arithmetic », Fibonacci Quarterly,‎ 2013 (arXiv 1207.4497, lire en ligne)

[:0-12] 1 2 Jean-Paul Delahaye, « Des suites exotiques pour écrire les nombres », Pour la Science, n^o 568,‎ février 2025, p. 74

[13] (en) T. Idziaszek, « Efficient algorithm for multiplication of numbers in Zeckendorf representation », FUN 2021,‎ 2021 (lire en ligne)

[14] Ces mots sont dits "binaires" car ce langage n'utilise que deux "lettres" : 0 et 1.

[15] La dernière "lettre" en partant de la droite étant nécessairement "1".

[16] Christine Solnon, Théorie des langages (Cours), Lyon, LIRIS, 30 p. (lire en ligne [PDF]), chap. 3 (« Langages réguliers et Automates finis »), p. 15-24

[17] (en) Péter Hajnal, « A short note on Zeckendorf type numeration systems with negative digits allowed », Bulletin of the ICA, vol. 97,‎ 2023, p. 54-66 (lire en ligne [PDF])

[18] Julie Piraprez, Le théorème de Zeckendorf : généralisations et réciproques (Mémoire de fin d'études (Master)), Liège, Liège Université, 2024, 91 p. (lire en ligne [PDF])

[19] (en) Donald Knuth, « Negafibonacci Numbers and the Hyperbolic Plane », Paper presented at the annual meeting of the MAA, The Fairmont Hotel, San Jose, CA. 2008-12-11 [présentation en ligne].

[20] (en) M. W. Bunder, « Zeckendorf representations using negative Fibonacci numbers », Fibonacci Quarterly,‎ 1992 (lire en ligne [PDF])

[21] (en) Donald E. Knuth, « Fibonacci Multiplication », Applied Mathematics Letters, vol. 1, n^o 1,‎ 1988, p. 57-60 (DOI 10.1016/0893-9659(88)90176-0)

[22] Exercice 5.4.2-10 dans (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition].

[23] Aviezri S. Fraenkel, « Systems of Numeration », The American Mathematical Monthly, vol. 92, n^o 2,‎ 1985, p. 105–114 (ISSN 0002-9890, DOI 10.2307/2322638, lire en ligne, consulté le 14 janvier 2026)

[AS-24] Ce théorème est attribué à Alexander Ostrowski (1922). Voir : (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, MR 1997038, lire en ligne), Section 3.9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]