Category Archives: Suite

Théorême de Zeckendorf

Tout entier naturel N non nul peut s’écrire de manière unique comme la somme de nombres de Fibonacci non consécutifs.
On définit la suite de Fibonacci par :

$$(U_n)_{n \in \mathbb N} : \begin{cases} U_{n+2}=U_{n+1}+U_n\\ U_0=1 \;et \; U_1=2\end{cases}$$

Les premiers termes de la suite sont :
$F_0=1$ ; $F_1=2$ ; $F_2=3$ ; $F_3=5$ ; $F_4=8$ ; $F_5=13$ ; $F_6=21$ ; $F_7=34$ ; $F_8=55$ ; $F_9=89$ ; $F_{10}=144$ $ …$

1ère remarque : traditionnellement les premiers termes de la suite de Fibonacci sont : 0 ; 1 ; 1; 2 ; 3 ; 5 ; 8 ; 13 … mais vu que le théorème ne concerne que les entiers naturels non nuls, nous faisons démarrer la suite de Fibonacci par 1.

2nde remarque : La somme peut être réduite à un seul nombre, si le nombre correspond à un nombre de Fibonacci.
Par exemple s’il on cherche la décomposition de 34 : $34=F_7$ et on s’arrête là !

3ème remarque : on considère que la décomposition de N se fera dans l’ordre croissant, ainsi on écrira $N= {\displaystyle \sum_{k=1}^n F_{C_k}}$ avec $C_{k+1}>C_{k}$ ce qui implique aussi que la décomposition est formée de nombres de Fibonacci distincts deux à deux.
4ème remarque : il est impératif que les nombres de Fibonacci ne soient pas consécutifs, en effet s’il on prend le nombre 100 :
$$100 = 1 + 2 + 8 +  89 = \overbrace{F_0 + F_1} + F_4 + F_9$$ qui est une somme où deux termes sont consécutifs : $F_0$ et $F_1$
$$100 = 3 + 8 + 34 + 55 = F_2 + F_4 + \overbrace{F_7 + F_8}$$ qui est une somme où deux termes sont consécutifs : $F_7$ et $F_8$
$$100 = 3 + 8 + 89 = F_2 + F_4 + F_9$$ qui cette fois-ci est bien une somme de termes non consécutifs.

Existence : preuve par récurrence
Pour $N=1$ on a  $1=F_0$ ce qui est vérifié

Pour $N=2$ on a $2=F_1$ qui est vérifié

Pour $N=3$ on a $3=F_2$ qui est vérifié

Et surtout pour $N=4$ on a $4=1+3=F_0+F_2$ qui est bien une somme de termes non consécutifs

On suppose que l’hypothèse est vérifiée au rang N-1 et cherchons à démontrer qu’elle l’est également au rang N

Rappelons que la suite $(U_n)$ est croissante et non majorée (la suite de Fibonacci tend vers $+\infty$ quand n tend vers $+\infty$) donc il existe un k tel que $F_k \leq{N}<F_{k+1}$

Soit $N=F_k$ et la démonstration est terminée,

soit $F_k<N$, il existe ainsi r tel que $F_k + r = N$ et donc $r=N-F_k$

r étant strictement plus plus petit que N alors d’après l’hypothèse de récurrence, r s’écrit comme la somme de nombres de Fibonacci non consécutifs, soit : $r=F_{r_0}+…+ F_{r_n}$ ainsi $N=F_{r_0}+…+ F_{r_n} + F_k $, il reste donc à démontrer que $F_{r_n}$ et $F_k $ ne sont pas consécutifs.

Rappelons qu’on a $F_k \leq{N}<F_{k+1}$ donc $F_k+r<F_{k+1}$ or d’après la définition de la suite de Fibonacci, $F_{k+1}=F_k+F_{k-1}$ ainsi $F_k+r<F_k+F_{k-1}$ soit $r<F_{k-1}$ ou encore $r=F_{r_0}+…+ F_{r_n}<F_{k-1}$ ce qui entraîne que $F_{r_n}<F_{k-1}<F_k$ ou encore que $F_{r_n}$ et $F_k $ ne peuvent être consécutifs.

Unicité : preuve par récurrence

On a bien $1=F_0$ ; $2=F_1$ ; $3=F_2$ et même $4=1+3=F_0+F_2$ décomposés de manière unique

On suppose que l’hypothèse de récurrence est vérifiée jusqu’au rang N-1, vérifions la au rang N

D’après l’existence démontrée ci-dessus, nous avons : $N= {\displaystyle \sum_{k=1}^r F_{c_k}}= {\displaystyle \sum_{k=1}^s F_{d_k}}$

Prenons les éléments maximaux de ces écritures et démontrons qu’ils sont égaux :

L’élément maximal est par définition le dernier nombre de Fibonacci de chaque décomposition, soit : $F_{c_r}$ et $F_{d_s}$. On a donc deux hypothèses, soit $c_r=d_s$ ou soit $c_r \neq{d_s}$

  •  $c_r=d_s$ et donc $F_{c_r}$ = $F_{d_s} $ donc $N=M+F_{c_r}=M+F_{d_s}$ et $M$ étant un nombre strictement inférieur à $N$, il se décompose de manière unique. Ainsi  $N$ est décomposé de manière unique.
  • $c_r \neq{d_s}$, prenons $c_r \leq{d_s}$, d’après ce qui a été dit plus haut on a $N<F_{c_r+1} \leq{F_{d_s}} \leq{N}$ ce qui est absurde et qui termine la démonstration.