Ouvrir le menu principal
Zeckendorf representations.svg
Représentation de Zeckendorf des 160 premiers entiers. Les nombres de Fibonacci intervenant dans la représentation sont figurés par des rectangles.

Le théorème de Zeckendorf, dénommé ainsi d'après le mathématicien belge Édouard Zeckendorf, est un théorème de théorie additive des nombres qui garantit que tout entier naturel 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 .

Sommaire

Énoncé et exempleModifier

Théorème de Zeckendorf[1] — Pour tout entier naturel  , il existe une unique suite d’entiers  , avec   et  , tels que

 ,

  est le  -ième nombre de Fibonacci.

Par exemple,   est représenté par la somme vide. La représentation de Zeckendorf du nombre   est

 .

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

 
 
 
 
 
 

mais ces représentations contiennent des nombres de Fibonacci consécutifs. À toute représentation d'un entier  , on associe un mot binaire, dont la  -ième lettre est   si   figure dans la représentation de   et   sinon. Ainsi, aux représentations de   ci-dessus sont associés les mots :

 
 
 
 
 
 
 .

L'ensemble des mots binaires associés aux représentations de Zeckendorf forme un langage rationnel : ce sont le mot vide et les mots commençant par   et ne contenant pas deux   consécutifs. Une expression rationnelle de ce langage est

 .

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

Note historiqueModifier

Zeckendorf a publié sa démonstration du théorème en 1972[1], alors que l'énoncé était connu, sous le nom « 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é[2] en 1952, tout en attribuant la paternité à Zeckendorf. D'après Clark Kimberling[3], c'est un article de David E. Daykin[4], publié dans un journal prestigieux, qui a contribué à faire connaître le résultat et son auteur.

DémonstrationModifier

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

1. Existence : L'existence de la représentation se prouve par l'emploi de l'algorithme glouton ou par récurrence sur  .

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  , est strictement inférieure à  .

Représentation des premiers entiersModifier

Dans la table,   dénote la représentation de   sous forme de mot binaire.

   
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

 

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 » ou « Fibonacci impair ».

VariationsModifier

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

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

 

permet de calculer   à partir de   et de  . On a (voir la section correspondante de l'article sur les nombres de Fibonacci) :

 

La suite complète est   Donald Knuth a remarqué[5] 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 :

  •   ;
  •   ;
  •   ;
  •  .

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

Multiplication de FibonacciModifier

Donald Knuth[6] considère une opération de multiplication   d'entiers naturels   et   définie comme suit : étant donné les représentations   et   le produit de Fibonacci est l'entier  .

Par exemple, comme   et  , on a  .

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

Autres suitesModifier

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

Knuth[7] 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.

Aviezri Fraenkel a donné un énoncé général qui étend les théorèmes précédents[8] : Soit   une suite d'entiers. Tout entier naturel   a exactement une représentation de la forme

 ,

  sont des entiers naturels, pourvu que

 

pour  .

Système d'OstrowskiModifier

Tout nombre irrationnel   admet un développement en fraction continue  . Si l'on pose  ,  ,  ,   et  ,  , on a  . La suite   forme une base pour un système de numération :

Théorème d'Ostrowski[9] — Soit   un nombre irrationnel, et soit   la suite des dénominateurs des convergents de la fraction continue de  . Tout entier positif   s'écrit de manière unique sous la forme

 

où les   sont des entiers satisfaisant les trois conditions suivantes :

  1.   ;
  2.   pour   ;
  3. Pour  , si  , alors  .

Pour le nombre d'or, les   valent tous 1, les   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érencesModifier

(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. a b et c É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,‎ , p. 179–182.
  2. (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,‎ , p. 190-195.
  3. (en) Clark Kimberling, « Edouard Zeckendorf [1901–1983] », Fibonacci Quart., vol. 36, no 5,‎ , p. 416–418.
  4. (en) D. E. Daykin, « Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers », J. London Math. Soc., vol. 35,‎ , p. 143 -60.
  5. (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].
  6. (en) Donald E. Knuth, « Fibonacci Multiplication », Applied Mathematics Letters, vol. 1, no 1,‎ , p. 57-60 (DOI 10.1016/0893-9659(88)90176-0)
  7. Exercice 5.4.2-10 dans (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, , 2e éd. [détail de l’édition].
  8. (en) Aviezri S. Fraenkel, « Systems of Numeration », Amer. Math. Monthly, vol. 92, no 2,‎ , p. 105-114.
  9. Ce théorème est attribué à Alexander Ostrowski (1922). Voir : (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, (ISBN 0-521-82332-3, Math Reviews 1997038, lire en ligne), Section 3.9.

Voir aussiModifier

Articles connexesModifier

Liens externesModifier