Théorème de Zeckendorf[modifier | modifier le code]

En mathématiques, le théorème de Zeckendorf est un résultat sur la décomposition des entiers naturels en une somme de nombres de Fibonacci. ~~(Édouard Zeckendorf en 1972 et C. G. Lekkerkerker vingt ans plus tôt)^{[réf. nécessaire]}~~

Choisissons un entier, 43 par exemple, et essayons de l'écrire comme une somme de nombres de Fibonacci, chaque nombre pouvant être utilisé au plus une fois. Dans cette décomposition ne peuvent bien sûr figurer que les nombres de Fibonacci inférieurs à 43 c'est-à-dire 1, 2, 3, 5, 8, 13, 21 et 34. On trouve quatre manières différentes d'écrire 43 :

43 = 34 + 8 + 1
43 = 34 + 5 + 3 + 1
43 = 21 + 13 + 8 + 1
43 = 21 + 13 + 5 + 3 + 1

Dans cet exemple, on constate qu'il est non seulement possible d'écrire 43 comme une somme de nombres de Fibonacci deux à deux distincts mais qu'en plus il existe plusieurs façons de le faire. Le théorème de Zeckendorf affirme deux choses. D'une part qu'une telle décomposition existe pour n'importe quel entier positif, d'autre part qu'elle est unique si l'on y interdit la présence de nombres de Fibonacci consécutifs.

Énoncé[modifier | modifier le code]

On défini la suite $(F_{n})$ des nombres de Fibonacci par $F_{1}=F_{2}=1$ et $F_{n}=F_{n-1}+F_{n-2}$ pour $n\geqslant 2$ .

Théorème — Soit $N$ un entier naturel non nul. Il existe un unique $p$ -uplet d'entiers $(a_{1},a_{2},\ldots ,a_{p})$ tel que $N=F_{a_{1}}+F_{a_{2}}+\cdots +F_{a_{p}}$ , les $a_{k}$ vérifiant $a_{1}\geqslant 2$ et $a_{k}\geqslant a_{k-1}+2$ pour $2\leqslant k\leqslant p$ .

La décomposition $N=F_{a_{1}}+F_{a_{2}}+\cdots +F_{a_{q}}$ est appelée représentation de Zeckendorf de l'entier $N$ .

Démonstration

On prouve d'abord l'existence d'une décomposition pour un entier naturel $N$ en utilisant l'algorithme suivant :

Le plus grand terme de la décomposition est le plus grand nombre de Fibonacci $F$ $F$ inférieur ou égal à $N$ $N$ .
- Si $N=F$ le calcul s'arrête là.
- Sinon on appelle $F'$ $F'$ le plus grand nombre de Fibonacci inférieur ou égal à $N-F$ $N-F$ . $F'$ $F'$ est le deuxième plus grand terme de la décomposition.
  - Si $N-F=F'$ le calcul s'arrête là.
  - Sinon l'on appelle $F''$ $F''$ le plus grand nombre de Fibonacci inférieur ou égal à $N-(F+F')$ $N-(F+F')$ . $F''$ $F''$ est le troisième plus grand terme de la décomposition.
    - Si $N-(F+F')=F''$ le calcul s'arrête là.
    - Sinon l'on appelle $F^{(3)}$ $F^{(3)}$ le plus grand nombre de Fibonacci inférieur ou égal à $N-(F+F'+F'')$ $N-(F+F'+F'')$ . $F^{(3)}$ $F^{(3)}$ est le quatrième plus grand terme de la décomposition.
      - etc.

Cet algorithme se termine car la suite des nombres

u_{k}=N-\left(F+F'+\cdots +F^{(k)}\right)

est une suite strictement décroissante d'entiers positifs. De plus deux nombres de Fibonacci consécutifs ne peuvent figurer dans la décomposition puisque...

Code de Fibonacci[modifier | modifier le code]

Article détaillé : Codage de Fibonacci.

La représentation de Zeckendorf est utilisée en théorie des codes sous le nom de code de Fibonacci : on associe à l'entier $N$ dont la représentation de Zeckendorf est $F_{a_{1}}+F_{a_{2}}+\cdots +F_{a_{p}}$ un mot de $a_{p}$ bits valant tous 0 sauf ceux aux positions $a_{p}$ et $a_{k}-1$ pour $2\leqslant k\leqslant p$ auxquels on donne la valeur 1 (on compte les bits de la gauche vers la droite). Ainsi dans le code de Fibonacci

43=1+8+34=1\times F_{2}+0\times F_{3}+0\times F_{4}+0\times F_{5}+1\times F_{6}+0\times F_{7}+0\times F_{8}+1\times F_{9}

s'écrit 100010011. D'après le théorème de Zeckendorf, la séquence « 11 » ne peut pas apparaître dans les $a_{p}-1$ premiers bits, on peut par conséquent s'en servir pour marquer la fin du mot. C'est le rôle du 1 ajouté en position $a_{p}$ qui, associé au 1 en position $a_{p}-1$ donne la séquence « 11 ». Cette technique permet d'encoder des entiers de longueur arbitraire.

Références[modifier | modifier le code]

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrep.html

Utilisateur:Flyingsquirrel/brouillon

Théorème de Zeckendorf[modifier | modifier le code]

Énoncé[modifier | modifier le code]

Code de Fibonacci[modifier | modifier le code]

Références[modifier | modifier le code]

Pages à relier à celle-ci[modifier | modifier le code]