Théorème de Zeckendorf

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Zeckendorf representations.png
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 sur la représentation des entiers comme somme de nombres de Fibonacci distincts.

Le théorème dit que tout entier positif N 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 N.

Énoncé et exemple[modifier | modifier le code]

Théorème de Zeckendorf[1] — Pour tout entier positif N, il existe une unique suite d’entiers positifs c_0,\ldots,c_k, avec c_0\ge2 et c_{i+1}>c_i+1, tels que

N=\sum_{i=0}^k F_{c_i},

F_n est le n-ième nombre de Fibonacci.

Par exemple, la représentation de Zeckendorf du nombre 100 est

100 = 89 + 8 + 3.

Le nombre 100 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 N, on associe 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, aux représentation de 100 ci-dessus sont associés les mots:

1000010100
1000010011
1000001111
110010100
110010011
110001111
101110100

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

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 1. Ainsi, le codage de Fibonacci du nombre 100 est 00101000011.

Note historique[modifier | modifier le code]

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, C. G. Lekkerkerker, a rédigé la preuve du théorème (et d'autres résultats) suite à un exposé de Zeckendorf, et l’a publié[2] en 1959, tout en attribuant la paternité à Zeckendorf. D'après Clark Kimberling[3], c'est un article de D. E. Daykin[4], publié dans un journal prestigieux, qui a contribué à faire connaître le résultat et son auteur.

Démonstration[modifier | modifier le code]

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

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

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

Lemme —  La somme de tout ensemble 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}.

Représentation des premiers entiers[modifier | modifier le code]

Dans la table, R(N) dénote la représentation de N sous forme de mot binaire.

N R(N)
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 » ou « Fibonacci impair ».

Variations[modifier | modifier le code]

Représentation par des nombres de Fibonacci d'indices négatifs[modifier | modifier le code]

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 des nombres de Fibonacci) :

F_{-n} = (-1)^{n+1} F_n.

La suite complète est \ldots ,-8 ,5, -3,2, -1,1,0,1,1,2,3,5,8,\ldots Donald Knuth a observé[5] que tout entier relatif est somme de nombres de Fibonacci d'indices 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)
  • 0 est représenté par la somme vide.

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[modifier | modifier le code]

Donald Knuth[6] 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}^kF_{c_i}\;(c_i\ge2) et b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2) le produit de Fibonacci est l'entier a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{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.

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

Autres suites[modifier | modifier le code]

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.

A. Fraenkel (en) a donné un énoncé général qui étend les théorèmes précédents[8] : 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_ku_k+d_{k-1}u_{k-1}+\cdots+d_1u_1+d_0u_0,

d_k,\ldots,d_0 sont des entiers naturels, pourvu que

 d_iu_i+d_{i-1}u_{i-1}+\cdots+ d_0u_0 < u_{i+1}

pour i\ge0.

Système d'Ostrowski[modifier | modifier le code]

Tout nombre irrationnel \alpha 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_np_{n-1}+p_{n-2}, q_n=a_nq_{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[9] — Soit \alpha un nombre irrationnel, et soit (q_n) la suite des dénominateurs des convergents de la fraction continue de \alpha. Tout entier positif N s'écrit de manière unique sous la forme

N=b_kq_k+\cdots+b_0q_0

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

  1. 0\le b_0< a_1
  2. 0\le b_i\le a_{i+1} pour i>0
  3. 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 son distincts et non consécutifs.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  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,‎ 1972, p. 179–182
  2. 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
  3. Clark Kimberling, « Edouard Zeckendorf [1901–1983] », Fibonacci Quart., vol. 36, no 5,‎ 1998, p. 416–418
  4. D. E. Daykin,, « Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers », Journal of the London Mathematical Society, vol. 35,‎ 1960, p. 143 -60
  5. Knuth, Donald. "Negafibonacci Numbers and the Hyperbolic Plane" Paper presented at the annual meeting of the Mathematical Association of America, The Fairmont Hotel, San Jose, CA. 2008-12-11 <http://www.allacademic.com/meta/p206842_index.html>
  6. (en) Donald E. Knuth, « Fibonacci Multiplication », Applied Mathematics Letters, vol. 1, no 1,‎ 1988, p. 57-60 (lien DOI?)
  7. Exercice 5.4.2-10 dans : Donald E. Knuth (2005), The Art of Computer Programming, vol. 3 : Sorting and Searching, Second Edition, Addison-Wesley,‎ 2005 (ISBN 0-201-89685-0, résumé)
  8. Aviezri S. Fraenkel, « Systems of Numeration », The American Mathematical Monthly, vol. 92, no 2,‎ 1985, p. 105-114
  9. Ce théorème est attribué à Ostrowski (1922). Voir : Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge University Press,‎ 2003 (ISBN 0-521-82332-3), Section 3.6

(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)

Liens externes[modifier | modifier le code]