Entier de Fibonacci

[Crono]

bonjour à tous

il me semble que je me trouve devant un petit problème qui requiert un raisonnement par analyse et synthèse, ce que decidemment je n'arriverai pas....toutefois je n'en suis pas sur..

il s'agit de démontré que tout entier >0 peut s'écrire de facon unique comme somme de nombres de fibonacci distincts non consécutifs (définis par F0=0, F1=1 et F(n+2)=F(n)+F(n+1) je rappele en cas de trous... ^^)

voila si vous pouviez m'apporter un peu d'aide j'en serais ravi
merci beaucoup et bon dimanche :)

[daiski]

c'est pas si facile , j'ai déjà rencontré j'ai des idées y'a de la récurrence quelque part , je te dirai plus tard.

deux liens résumant les principales relations vérifiées par ces nombres :

http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Fibonacc.htm

http://mathserver.sdu.edu.cn/mathency/math/f/f121.htm

[alben]

Bonjour,

Que signifie exactement non consécutifs. Si n est la somme de 3 nombres, est-ce que 2 consécutifs et un éloigné marche ?
Si oui, alors la décomposition n'est pas unique pour au moins les nombres de la suite au delà de 3 :
Si non, 5 n'a pas de décomposition autre que 5+0 et si on l'admet alors 8 en a deux : 0+8 et le premier 1 +2 + 5

[Crono]

donc voila!

il s'agit donc bien de prouver que tout entier se décompose de facon unique comme somme d'entier de Fibonacci, a partir de F2=1

on ne peut donc ni utiliser le F0=0 qui donnerait plein de nouvelles possibilités ni le F1=1 qui donnerait beaucoup de solutions du style
n=F(p)+F1=F(p)+F2

toujours est-il que je n'y arrive toujours pas...
merci d'avance et bonne soirée a tous :)

[Amine.MASS]

bonjour,
on a eu ce probléme dans un devoir surveillé mais avec des questions détaillé ça devient plus simple,je te donnerai les pistes a suivre:




on va montrer que tout peut s'ecrire d'une manière unique avec ( ) des éléments de {0,1} tq
(la condition sur les est équivalente a ce que les nmbrs de fibonacci soient distincts non consécutifs )


I-l'existence
1/montre par recurrence sur n que la prop est vrai(seulment l'existence) pour tout
( la rec est sur n et non k)

2/soit : montre qu'il existe tq
(ça aussi ça s montre par recurrence sur k)
3/en déduire l'existence pour tout


I-l'unicité

étant donné un et ( ) avec les conditions déja vue ( et les ..etc)
montre que
(par recurrence sur n)


*en déduire l'unicité

j'espere que c'est claire,n'hésite pas a demander si tu t bloque dans une question . bon courage
Cordialement,Amine

[Crono]

je te remercie beaucoup, je vais tester ceci ce week end et je reviendrai sur le forum si j'ai quelques problèmes

bonne soirée :)

[Crono]

j'ai finalement pu trouver un peu de temps pour y reflechir...

alors pour la premiere récurrence, il faut initialiser a k=Fn
prendre l'hypothese de rec : k k = sigma(ai.Fi)pour i de 2 a n
et prouver ke k k=sigma(ai.Fi) pour i de 2 a n-1 ??

désolé c pas très compréhensible mais je ne sais pas faire les écritures des sigma, il faut des commandes spéciales?
Bref, s'agit-il d'une réccurence décendante sur n?

en fait je ne vois pas pourquoi on ne fait pas une récurrence sur k, puisqu'on veut montrer que tout entier se décompose de cette facon, on suppose un k qui le fait et on montre que l'entier suivant se décompose lui aussi comme ca, soit une récurrence sur k...?

Sinon pour montrer qu'il existe n/ k
merci d'avance et bon dimanche

[Amine.MASS]

désolé c pas très compréhensible mais je ne sais pas faire les écritures des sigma, il faut des commandes spéciales?

bonsoir,
pour écrire des symboles mathématiques cherche dans google a propos de Latex

alors pour la premiere récurrence, il faut initialiser a k=Fn
prendre l'hypothese de rec : k k = sigma(ai.Fi)pour i de 2 a n
et prouver ke k k=sigma(ai.Fi) pour i de 2 a n-1 ??

Bref, s'agit-il d'une réccurence décendante sur n?

je ne vois pas comment faire une reccurence décendante!!je propose une reccurence forte:
pour n=2 ,soit donc k=0 ou k=1 (car )
c'est simple de vérifier que la prop est vrai
-soit IN ( ):on suppose que la prop est vrai pour tt
*soit :
-si :alors k s'ecrit comme k= (avec )

-si :alors
donc
k-Fn=
*si :
alors on pose donc k=
*si alors

donc
(car et on pose )

(n'oublie pas que la condition est vérifiée )
remarque:il fallait changer la famille pour ne pas les confondre

[Amine.MASS]

en fait je ne vois pas pourquoi on ne fait pas une récurrence sur k, puisqu'on veut montrer que tout entier se décompose de cette facon, on suppose un k qui le fait et on montre que l'entier suivant se décompose lui aussi comme ca, soit une récurrence sur k...?

c'était juste une proposition de faire une reccurence sur n(c'est pas l'unique solution),peut étre c'est faisable sur k mais je ne vois pas comment :triste:

Sinon pour montrer qu'il existe n/ k<Fn, ne suffit-il pas de dire que la suite de fibonacci tend vers l'infini, et donc qu'il existera toujours un entier n tel que pour tout k, k<Fn ?

tu as raison c'est plus simlpe :++:
allez bon courage
Cordialement,Amine

[Crono]

ok pour la récurrence forte, merci beaucoup
apres pour l'unicité je suis pas très sur de ma récurrence, j'ai fait une récurrence forte sur n

avec Hypothese de rec : pour tout m
je vais appeler A le sigma(ai.Fi) :

A(i=2...n)=A(i=2....n-1)+ an.Fn

*si an=0 c'est facile

*si an=1, alors a(n-1)=0
et A(i=2...n)=A(i=2....n-2)+Fn
et en utilisant l'hypothese de rec A(i=2...n-2)< Fn-1
donc A(i=2...n) = A(i=2....n-2)+Fn < Fn-1+Fn = Fn+1

Par contre, je ne vois pas en quoi cela traduit l'unicité....
merci encore et bonne soirée :)

[Amine.MASS]

saluut,
on suppose que avec les hypothéses ...
montrons par reccurence forte descendante que

-pour p=n on a :
puisque et
alors et sont le quotient de la div euc de k par
par unicité du quotient on a


-soit ,on suppose que donc:

puisque et
alors et sont les quotient de la div euc de .....
d'ou