Théorème de Zeckendorf

Représentation de Zeckendorf des 89 premiers entiers. Les largeurs des rectangles sont des nombres de Fibonacci Fi, alors que les hauteurs correspondantes ont Fi-1.
Les rectangles de la mème couleur sont congruents.

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

Théorème de Zeckendorf[1] — Pour tout entier naturel N, il existe une unique suite d’entiers c0, ... , ck, avec c 0 ≥ 2 {\displaystyle c_{0}\geq 2} et ci+1 > ci + 1, tels que

N = ∑ i = 0 k F c i {\displaystyle N=\sum _{i=0}^{k}F_{c_{i}}} ,

où Fn est le n-ième nombre de Fibonacci.

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

100 = 89 + 8 + 3 {\displaystyle 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 {\displaystyle 100=89+8+2+1}
100 = 89 + 5 + 3 + 2 + 1 {\displaystyle 100=89+5+3+2+1}
100 = 55 + 34 + 8 + 3 {\displaystyle 100=55+34+8+3}
100 = 55 + 34 + 8 + 2 + 1 {\displaystyle 100=55+34+8+2+1}
100 = 55 + 34 + 5 + 3 + 2 + 1 {\displaystyle 100=55+34+5+3+2+1}
100 = 55 + 21 + 13 + 8 + 3 {\displaystyle 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 Fn figure dans la représentation de N et 0 sinon. Ainsi, aux représentations de 100 ci-dessus sont associés les mots :

1000010100 {\displaystyle 1000010100}
1000010011 {\displaystyle 1000010011}
1000001111 {\displaystyle 1000001111}
110010100 {\displaystyle 110010100}
110010011 {\displaystyle 110010011}
110001111 {\displaystyle 110001111}
101110100 {\displaystyle 101110100} .

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 1 et ne contenant pas deux 1 consécutifs. Une expression rationnelle de ce langage est

0 + 1 ( 0 + 01 ) ∗ {\displaystyle 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 1. Ainsi, le codage de Fibonacci du nombre 100 est 00101000011.

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é[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émonstration

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 N.

Deux preuves de l'existence
Première preuve
On raisonne par récurrence bien fondée sur l'entier naturel N. Si N est nul, il est représenté par la somme vide. Sinon, soit Fk, avec k ≥ 2 {\displaystyle k\geq 2} , le plus grand nombre de Fibonacci inférieur ou égal à N et soit M = N − F k {\displaystyle M=N-F_{k}} . Par hypothèse de récurrence, M possède une représentation. Alors, pour tout nombre F ℓ {\displaystyle F_{\ell }} de cette représentation, F k + F ℓ ≤ F k + M = N < F k + 1 = F k + F k − 1 {\displaystyle F_{k}+F_{\ell }\leq F_{k}+M=N<F_{k+1}=F_{k}+F_{k-1}} donc F ℓ < F k − 1 {\displaystyle F_{\ell }<F_{k-1}} . La représentation de M, augmentée de Fk, est donc bien une représentation de N.
Seconde preuve
On raisonne par récurrence 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 + ⋯ + F i s {\displaystyle n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}} avec 4 ≤ i 1 {\displaystyle 4\leq i_{1}} et ∀ j , i j + 1 ≥ i j + 2 {\displaystyle \forall j,i_{j+1}\geq i_{j}+2} , alors :
    n + 1 = F 2 + F i 1 + F i 2 + ⋯ + F i s {\displaystyle n+1=F_{2}+F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}}
  • Si n = F 3 + F 5 + ⋯ + F 2 r − 1 + F i r + F i r + 1 + ⋯ + F i s {\displaystyle n=F_{3}+F_{5}+\cdots +F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}} avec i r ≥ 2 r + 2 {\displaystyle i_{r}\geq 2r+2} et ∀ j , i j + 1 ≥ i j + 2 {\displaystyle \forall j,i_{j+1}\geq i_{j}+2} (et éventuellement i s = 2 r − 1 {\displaystyle i_{s}=2r-1} auquel cas les termes F i r + F i r + 1 + ⋯ + F i s {\displaystyle F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}} n'existent pas). Alors :
    n + 1 = F 2 r + F i r + F i r + 1 + ⋯ + F i s {\displaystyle n+1=F_{2r}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}}
  • Si n = F 2 + F 4 + ⋯ + F 2 r − 2 + F i r + F i r + 1 + ⋯ + F i s {\displaystyle n=F_{2}+F_{4}+\cdots +F_{2r-2}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}} avec i r ≥ 2 r + 1 {\displaystyle i_{r}\geq 2r+1} et ∀ j , i j + 1 ≥ i j + 2 {\displaystyle \forall j,i_{j+1}\geq i_{j}+2} (et éventuellement i s = 2 r − 2 {\displaystyle i_{s}=2r-2} auquel cas les termes F i r + F i r + 1 + ⋯ + F i s {\displaystyle F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}} n'existent pas). Alors :
    n + 1 = F 2 r − 1 + F i r + F i r + 1 + ⋯ + F i s {\displaystyle n+1=F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}}
Ainsi, n + 1 {\displaystyle 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 Fj, est strictement inférieure à Fj+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 Fj. Par hypothèse de récurrence, la somme des éléments restants est strictement inférieure à Fj-1, donc la somme totale est strictement inférieure à Fj-1 + Fj = Fj+1.
Seconde démonstration
Si n = F i 1 + F i 2 + ⋯ + F i s {\displaystyle n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}} avec ∀ j , i j + 1 ≥ i j + 2 {\displaystyle \forall j,i_{j+1}\geq i_{j}+2} . Alors :
  • si is est pair :
    F i 1 + F i 2 + ⋯ + F i s − 1 ≤ F i s − 2 + F i s − 4 + ⋯ + F 2 {\displaystyle F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leq F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{2}}
    donc :
    F i 1 + F i 2 + ⋯ + F i s − 1 < F i s − 2 + F i s − 4 + ⋯ + F 2 + 1 = F i s − 1 {\displaystyle 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 is est impair :
    F i 1 + F i 2 + ⋯ + F i s − 1 ≤ F i s − 2 + F i s − 4 + ⋯ + F 3 {\displaystyle F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leq F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{3}}
    donc :
    F i 1 + F i 2 + ⋯ + F i s − 1 < F i s − 2 + F i s − 4 + ⋯ + F 3 + 1 = F i s − 1 {\displaystyle 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 ≤ n < F i s + F i s − 1 = F i s + 1 {\displaystyle F_{i_{s}}\leq n<F_{i_{s}}+F_{i_{s}-1}=F_{i_{s}+1}}
Preuve de l'unicité

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

Représentation des premiers entiers

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 ⋯ {\displaystyle 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

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 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

permet de calculer F n − 2 {\displaystyle F_{n-2}} à partir de Fn et de F n − 1 {\displaystyle F_{n-1}} . On a (voir la section correspondante de l'article sur les nombres de Fibonacci) :

F − n = ( − 1 ) n + 1 F n . {\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}

La suite complète est … , − 8 , 5 , − 3 , 2 , − 1 , 1 , 0 , 1 , 1 , 2 , 3 , 5 , 8 , … {\displaystyle \ldots ,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,\ldots } 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 :

  • − 11 = F − 4 + F − 6 = ( − 3 ) + ( − 8 ) {\displaystyle -11=F_{-4}+F_{-6}=(-3)+(-8)}  ;
  • 12 = F − 2 + F − 7 = ( − 1 ) + 13 {\displaystyle 12=F_{-2}+F_{-7}=(-1)+13}  ;
  • 24 = F − 1 + F − 4 + F − 6 + F − 9 = 1 + ( − 3 ) + ( − 8 ) + 34 {\displaystyle 24=F_{-1}+F_{-4}+F_{-6}+F_{-9}=1+(-3)+(-8)+34}  ;
  • − 43 = F − 2 + F − 7 + F − 10 = ( − 1 ) + 13 + ( − 55 ) {\displaystyle -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 Fn 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[6] considère une opération de multiplication a ∘ b {\displaystyle a\circ b} d'entiers naturels a {\displaystyle a} et b {\displaystyle b} définie comme suit : étant donné les représentations a = ∑ i = 0 k F c i ( c i ≥ 2 ) {\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)} et b = ∑ j = 0 l F d j ( d j ≥ 2 ) {\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)} le produit de Fibonacci est l'entier a ∘ b = ∑ i = 0 k ∑ j = 0 l F c i + d j {\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}} .

Par exemple, comme 2 = F3 et 4 = F4 + F2, on a 2 ∘ 4 = F 3 + 4 + F 3 + 2 = 13 + 5 = 18 {\displaystyle 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[1].

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

Aviezri Fraenkel 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 < ⋯ {\displaystyle 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 + ⋯ + d 1 u 1 + d 0 u 0 {\displaystyle N=d_{k}u_{k}+d_{k-1}u_{k-1}+\cdots +d_{1}u_{1}+d_{0}u_{0}} ,

où d k , … , d 0 {\displaystyle d_{k},\ldots ,d_{0}} sont des entiers naturels, pourvu que

d i u i + d i − 1 u i − 1 + ⋯ + d 0 u 0 < u i + 1 {\displaystyle d_{i}u_{i}+d_{i-1}u_{i-1}+\cdots +d_{0}u_{0}<u_{i+1}}

pour i ≥ 0 {\displaystyle i\geq 0} .

Système d'Ostrowski

Article connexe : Numération d'Ostrowski.

Tout nombre irrationnel α admet un développement en fraction continue α = [ a 0 , a 1 , a 2 , … ] {\displaystyle \alpha =[a_{0},a_{1},a_{2},\ldots ]} . Si l'on pose p − 2 = 0 {\displaystyle p_{-2}=0} , p − 1 = 1 {\displaystyle p_{-1}=1} , q − 2 = 1 {\displaystyle q_{-2}=1} , q − 1 = 0 {\displaystyle q_{-1}=0} et p n = a n p n − 1 + p n − 2 {\displaystyle p_{n}=a_{n}p_{n-1}+p_{n-2}} , q n = a n q n − 1 + q n − 2 {\displaystyle q_{n}=a_{n}q_{n-1}+q_{n-2}} , on a p n / q n = [ a 0 , … , a n ] {\displaystyle p_{n}/q_{n}=[a_{0},\ldots ,a_{n}]} . La suite ( q n ) {\displaystyle (q_{n})} forme une base pour un système de numération :

Théorème d'Ostrowski[9] — Soit α un nombre irrationnel, et soit (qn) 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 + ⋯ + b 0 q 0 {\displaystyle N=b_{k}q_{k}+\cdots +b_{0}q_{0}}

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

  1. 0 ≤ b 0 < a 1 {\displaystyle 0\leq b_{0}<a_{1}}  ;
  2. 0 ≤ b i ≤ a i + 1 {\displaystyle 0\leq b_{i}\leq a_{i+1}} pour i > 0 {\displaystyle i>0}  ;
  3. Pour i > 0 {\displaystyle i>0} , si b i = a i + 1 {\displaystyle b_{i}=a_{i+1}} , alors b i − 1 = 0 {\displaystyle b_{i-1}=0} .

Pour le nombre d'or, les ai valent tous 1, les qn 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. ↑ 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, Cambridge University Press, , 571 p. (ISBN 0-521-82332-3, MR 1997038, lire en ligne), Section 3.9.

Voir aussi

Articles connexes

Liens externes

  • icône décorative Portail des mathématiques