Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

**Flyingsquirrel** · 09/03/2009, 22h28

Bonsoir,

En me baladant sur wikipedia j'ai découvert un théorème qui s'appelle le théorème de Zeckendorf et qui affirme ceci : Tout entier strictement positif peut être décomposé de manière unique en une somme de nombres de Fibonacci¹ non-consécutifs et deux à deux distincts.

Dit autrement, pour tout entier $\text{[math]}$ , il existe un unique $\text{[math]}$ -uplet d'entiers $\text{[math]}$ tel que

$\text{[math]}$

avec $\text{[math]}$ et $\text{[math]}$ pour $\text{[math]}$ .

Quelques exemples de décomposition : $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ ...

Étonnant, non ?

Ceux que cela amuse peuvent essayer de démontrer le théorème. Il n'est pas trop difficile de prouver qu'un entier naturel quelconque peut se décomposer comme décrit plus haut. Établir l'unicité de la décomposition est par contre plus ardu. Pour ce faire on pourra utiliser (voire même montrer) ce résultat :

Cliquez pour afficher

_____________________
(1) Les nombres de Fibonacci sont les termes de la suite $\text{[math]}$ définie par $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ pour $\text{[math]}$ . Les treize premiers termes sont 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 et 144.

**KerLannais** · 30/05/2009, 23h41

Salut,

C'est vrai que c'est très joli comme résultat, je voulais juste faire une toute petite remarque
$\text{[math]}$
et pas 27

**mx6** · 31/05/2009, 00h26

Je suis sidéré qu'on peut démontrer ce résultat, et non pas la conjecture de Goldbach qui a l'air tout simple.......

**mx6** · 31/05/2009, 19h08

Bonjour,

Après un long moment de tentatives, j'ai enfin réussi par récurrence !

Démontrons que pour tout entier n tel que $\text{[math]}$ est la somme de nombres $\text{[math]}$ d'indices distincts tel que $\text{[math]}$ .

Pour $\text{[math]}$ , $\text{[math]}$ .

On suppose que la propriété est vraie pour un certain rang $\text{[math]}$ .

On doit envisager deux cas, si $\text{[math]}$ alors la propriété découle directement de l'hypothèse.

Il reste à étudier le cas suivant : $\text{[math]}$ , donc on peut écrire $\text{[math]}$ sous la forme de $\text{[math]}$ avec $\text{[math]}$ entier, et comme $\text{[math]}$ donc $\text{[math]}$
$\text{[math]}$ peut donc s'écrire sous la forme de somme de nombres de Fibonacci distincts avec $\text{[math]}$ .
$\text{[math]}$ est donc la somme de nombres de Fibonacci, d'indices distincts avec $\text{[math]}$ .

A voir en vidéo sur Futura · Aujourd'hui

**Flyingsquirrel** · 31/05/2009, 19h23

Envoyé par mx6

Démontrons que pour tout entier n tel que $\text{[math]}$ est...

C'est volontaire le $\text{[math]}$ qui apparait des deux côtés de l'inégalité ?

**mx6** · 31/05/2009, 19h29

Oups, désolé pour la confusion, au lieu de $\text{[math]}$ posons $\text{[math]}$ !

Indice pour l'unicité, par l'absurde ?

**Flyingsquirrel** · 31/05/2009, 19h39

Envoyé par mx6

Oups, désolé pour la confusion, au lieu de $\text{[math]}$ posons $\text{[math]}$ !

D'accord. Et c'est au lecteur de faire le remplacement tout au long de la démo ?

(et puis tu as oublié de tenir compte du fait que les $\text{[math]}$ sont non consécutifs)

Indice pour l'unicité, par l'absurde ?

Par exemple, oui.

**mx6** · 31/05/2009, 19h48

Envoyé par Flyingsquirrel

D'accord. Et c'est au lecteur de faire le remplacement tout au long de la démo ?

(et puis tu as oublié de tenir compte du fait que les $\text{[math]}$ sont non consécutifs

Je suis d'accord que ça manque de rigueur, mais l'idée est la

(en même temps, je suis pressé par le Bac).

Je bloque pour l'unicité, je vais essayer ^^

**mx6** · 01/06/2009, 00h30

Un indice please ! ^^

invitef1b93a42 · 01/06/2009, 01h15

Tu prends deux nombres a et b ayant la même décomposition de Zeckendorf et étant distincts, tu montres alors que $\text{[math]}$ . Commence par soustraire à $\text{[math]}$ et à $\text{[math]}$ les éléments de leur somme en commun et de-là tu travailles sur les 2 nouveaux nombres formés $\text{[math]}$ .

**mx6** · 01/06/2009, 09h22

Oki je vais y refléchir !

Voici un bon exo sur Fibo : Découverte de Lagrange

Si à tout nombre de Fibonacci on associe son dernier chiffre, on obtient alors une suite périodique de période 60.

invite2220c077 · 01/06/2009, 09h42

Ou :

i) Montrer que pour tout $\text{[math]}$ , il existe un nombre de Fibonacci se finissant par $\text{[math]}$ zéros.

ii) Montrer que pour tout $\text{[math]}$ , $\text{[math]}$ n'est pas premier.

invite2220c077 · 01/06/2009, 09h53

Pour ton exercice mx6 :

On considère la suite suivante : 1,1, 2, 3, 5, 8, 3, 1, 4 ... où chaque terme est la somme des deux précédents modulo 10. Il suffit d'utiliser le principe des tiroirs. C'est direct.

invite2220c077 · 04/06/2009, 17h50

Salut,

Pour infos, on peut généraliser ce théorème. On définit une suite $\text{[math]}$ de premiers termes $\text{[math]}$ et $\text{[math]}$ . Alors pour tout naturel $\text{[math]}$ , il existe une unique suite $\text{[math]}$ d'indices tels que $\text{[math]}$ , où les termes sont deux à deux distincts.

**mx6** · 04/06/2009, 18h03

Il me semble que ca reste la même démo, car en aucun cas, on a utilisé une propriété de la suite de Fibonacci. Mais bien vu l'idée ^^

Sinon, t'as su démontré l'unicité ?

invite2220c077 · 04/06/2009, 18h09

C'est lourd qu'on ne puisse pas éditer après 5min ... Je voulais parler de la suite de Fibonacci généralisée d'ordre k, c'est-à-dire $\text{[math]}$ avec $\text{[math]}$

**mx6** · 04/06/2009, 18h25

Si $\text{[math]}$ ca ne marche pas ! Je pense qu'il y des conditions à mettre !

**Flyingsquirrel** · 04/06/2009, 18h53

Envoyé par mx6

tu peux poster la démo de l'unicité de ton post sur Zeckendoff

Il y a suffisamment d'indications dans ce fil...

Envoyé par Equinoxx

Tu prends deux nombres a et b ayant la même décomposition de Zeckendorf et étant distincts, tu montres alors que $\text{[math]}$ . Commence par soustraire à $\text{[math]}$ et à $\text{[math]}$ les éléments de leur somme en commun et de-là tu travailles sur les 2 nouveaux nombres formés $\text{[math]}$ .

... mais je peux en ajouter une. Si l'on a

$\text{[math]}$
$\text{[math]}$

(avec les conditions qui vont bien sur les $\text{[math]}$ et les $\text{[math]}$ ) alors soit $\text{[math]}$ , soit $\text{[math]}$ puisque, par définition de $\text{[math]}$ et de $\text{[math]}$ , ces deux nombres n'ont pas de nombre de Fibonacci en commun dans leur décomposition. Ensuite il faut utiliser ceci :

Envoyé par Flyingsquirrel

Avec les conditions données plus haut sur les $\text{[math]}$ on a $\text{[math]}$ .

**Thorin** · 04/06/2009, 19h22

Pour mx6, l'unicité :

On se donne 2 décompositions distinctes de n.

$\text{[math]}$

comme les suites a et b ne sont pas égales, on peut supposer que $\text{[math]}$ et $\text{[math]}$ ne sont pas égaux (s'ils le sont, on les retranche...)
on suppose aussi $\text{[math]}$

on utilise le résultat donné au premier post :
$\text{[math]}$ et $\text{[math]}$ car $\text{[math]}$ .
ainsi :
$\text{[math]}$

Oui, mais voilà... $\text{[math]}$ est le plus petit entier tel que le nombre de fibonacci lui étant associé majore $\text{[math]}$ (en effet, on a : $\text{[math]}$ , et si on prend un entier plus petit, l'inégalité est clairement fausse).
C'est donc le plus petit entier tel que le nombre de fibonacci qui lui est associé majore $\text{[math]}$ .
Or, on a : $\text{[math]}$
ce qui contredit ce que je viens de dire !
Sauf erreur (possible) de raisonnement.
Edit : j'ai tapé le message avant d'aller manger, je l'ai poté en revenant, mais entre temps, flyingsqirrel a répondu

**mx6** · 05/06/2009, 00h43

Oui, c'était si évident ^^ !

Flyingquirrel dans son premier post avait dit c'était "ardue", j'ai pensé à un truc de fou ^^

Merci !

**Thorin** · 05/06/2009, 18h54

C'est tout de même légèrement subtil

Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Re : Décomposition d'un entier en une somme de nombres de Fibonacci — théorème de Zeckendorf

Discussions similaires

Décomposer un entier en une somme d'entiers consécutifs

Déterminer si une opération sur deux nombres aboutit à un entier.

décomposition d'une courbe en somme de gaussiennes

Probabilité d'un nombre par rapport à un somme de 4 nombres!

nombres de fibonacci