Théorème de Zeckendorf

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 F_k, avec ${\displaystyle k\geq 2}$, le plus grand nombre de Fibonacci inférieur ou égal à N et soit ${\displaystyle M=N-F_{k}}$. Par hypothèse de récurrence, M possède une représentation. Alors, pour tout nombre ${\displaystyle F_{\ell }}$ de cette représentation, ${\displaystyle F_{k}+F_{\ell }\leq F_{k}+M=N<F_{k+1}=F_{k}+F_{k-1}}$ donc ${\displaystyle F_{\ell }<F_{k-1}}$. La représentation de M, augmentée de F_k, 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 ${\displaystyle n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}}$ avec ${\displaystyle 4\leq i_{1}}$ et ${\displaystyle \forall j,i_{j+1}\geq i_{j}+2}$, alors :

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

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

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

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

  ${\displaystyle n+1=F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}}$

Ainsi, ${\displaystyle n+1}$ admet aussi une décomposition.

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 ${\displaystyle n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}}$ avec ${\displaystyle \forall j,i_{j+1}\geq i_{j}+2}$. Alors :

• si i_s est pair :

  ${\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 :

  ${\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 i_s est impair :

  ${\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 :

  ${\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, ${\displaystyle F_{i_{s}}\leq n<F_{i_{s}}+F_{i_{s}-1}=F_{i_{s}+1}}$

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 ${\displaystyle k}$ pour lequel F_k apparaît (si la décomposition est non vide, c.-à-d. si ${\displaystyle N\neq 0}$) est entièrement déterminé par ${\displaystyle F_{k}\leq 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.