[MPSI] " Vagabondages fibonacciens"

[Anonyme]

Bonsoir,
J'ai un petit problème sur un DM de maths, le voici:
On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} = F_{n}
+ F_{n-1}
On me demande des choses que je sais faire :) , et des choses que je
ne sais pas faire :

- On me demande de calculer (F_{n})^2 - F_{n+1}*F_{n-1}
(surement pas recurrence forte, mais je connais juste le principe, je
ne sais pas comment ca se redige, d'une part ni comment on s'en sert
d'autre part. )
- On me demande de comparer phi et ( F_{n+1)*phi + F_{n}) / (
F_{n}*phi + F_{n-1}) , et je trouve que phi = ( F_{n+1)*phi + F_{n}) /
( F_{n}*phi + F_{n-1}), ce qui sera utile pour la question suivante
surement ...
- On me demande de montrer que pour tout n >0 ,
F_{2n+1} / F_{2n+1} < phi < F_{2n+1} / F_{2n}
Alors j'ai dit que phi = ( F_{n+1)*phi + F_{n}) / ( F_{n}*phi +
F_{n-1}) , et j'ai posé 2k = n, et j'ai aussi rappelé que F_{2n+1} =
F_{2n-1} + F_{2n} , mais j'ai l'impression de "tourner en rond" ...
et je trouve pas... si quelqu'un pouvait m'aider, ce serait sympa .

Merci

Fab

[Anonyme]

"Ghostux" a écrit dans le message de news:
414387aa$0$30396$636a15ce@news.free.fr...
> Bonsoir,
> J'ai un petit problème sur un DM de maths, le voici:
> On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
> On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} =
F_{n}
> + F_{n-1}

Désolé je me suis trompé, c'est F_{n+2} = F_{n} + F_{n+1}

[Anonyme]

Ghostux a écrit:
> Bonsoir,
> J'ai un petit problème sur un DM de maths, le voici:
> On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
> On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} = F_{n}
> + F_{n-1}
> On me demande des choses que je sais faire , et des choses que je
> ne sais pas faire :
>
> - On me demande de calculer (F_{n})^2 - F_{n+1}*F_{n-1}
> (surement pas recurrence forte, mais je connais juste le principe, je
> ne sais pas comment ca se redige, d'une part ni comment on s'en sert
> d'autre part. )
> - On me demande de comparer phi et ( F_{n+1)*phi + F_{n}) / (
> F_{n}*phi + F_{n-1}) , et je trouve que phi = ( F_{n+1)*phi + F_{n}) /
> ( F_{n}*phi + F_{n-1}), ce qui sera utile pour la question suivante
> surement ...
> - On me demande de montrer que pour tout n >0 ,
> F_{2n+1} / F_{2n+1} Alors j'ai dit que phi = ( F_{n+1)*phi + F_{n}) / ( F_{n}*phi +
> F_{n-1}) , et j'ai posé 2k = n, et j'ai aussi rappelé que F_{2n+1} =
> F_{2n-1} + F_{2n} , mais j'ai l'impression de "tourner en rond" ...
> et je trouve pas... si quelqu'un pouvait m'aider, ce serait sympa .
>
> Merci
>
> Fab
>
>

Bonjour

premièrement je pense juste pour les notations que tu devrais noter
F_n+2, ou F_(n+2), plutot que avec des accolades qui font penser à un
ensemble... enfin cela n'a pas d'importance ici.

Pour ta première question je ne pense pas que tu ai besoin de récurrence
forte, mais par contre il pourrait t'être utile pour commencer ta
récurence de connaitre la valeur de la différence.
Cela dit, il y a plus astucieux que la réccurence : tu pars de ta
différence au rang n+1 (F_n+1)^2 - F_n+2 * F_n et tu essayes en
remplacant astucieusement d'obtenir une relation avec ta différence au
rang n (par exemple, k * [ (F_n)^2 - ... ] , et ensuite tu dis que c'est
une suite géometrique dont tu peux donner la formule explicite).

Euh je pense sinon que ton inégalité est fausse, et ne serait ca pas
plutot :
F_2n+1/F_2n < phi < F_2n+2/F_2n+1 ??

--
albert

[Anonyme]

On Sun, 12 Sep 2004 10:28:11 +0200, albert junior wrote:
>premièrement je pense juste pour les notations que tu devrais noter
>F_n+2, ou F_(n+2), plutot que avec des accolades qui font penser à un
>ensemble... enfin cela n'a pas d'importance ici.

Ben non : c'est de la syntaxe (pseudo-)TeX, les accolades servant à
grouper un bloc de texte. F_n+2 s'afficherait
F + 2
n
et F_(n+2) deviendrait
F n + 2)
(

Seul F_{n+2} fait ce qui faut... ce qui se repère instantanément pour
qui a fait un peu de TeX.

[Anonyme]

"Ghostux" a écrit dans le message de news:
414387aa$0$30396$636a15ce@news.free.fr...
> Bonsoir,
> J'ai un petit problème sur un DM de maths, le voici:
> On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
> On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} = F_{n}
> + F_{n-1}
> On me demande des choses que je sais faire , et des choses que je
> ne sais pas faire :
>
> - On me demande de calculer (F_{n})^2 - F_{n+1}*F_{n-1}
> (surement pas recurrence forte, mais je connais juste le principe, je
> ne sais pas comment ca se redige, d'une part ni comment on s'en sert
> d'autre part. )
> - On me demande de comparer phi et ( F_{n+1)*phi + F_{n}) / (
> F_{n}*phi + F_{n-1}) , et je trouve que phi = ( F_{n+1)*phi + F_{n}) /
> ( F_{n}*phi + F_{n-1}), ce qui sera utile pour la question suivante
> surement ...
> - On me demande de montrer que pour tout n >0 ,
> F_{2n+1} / F_{2n+1} Alors j'ai dit que phi = ( F_{n+1)*phi + F_{n}) / ( F_{n}*phi +
> F_{n-1}) , et j'ai posé 2k = n, et j'ai aussi rappelé que F_{2n+1} =
> F_{2n-1} + F_{2n} , mais j'ai l'impression de "tourner en rond" ...
> et je trouve pas... si quelqu'un pouvait m'aider, ce serait sympa .
>
> Merci
>
> Fab
>
>

[Anonyme]

Frederic a écrit:
> On Sun, 12 Sep 2004 10:28:11 +0200, albert junior wrote:
>[color=green]
>>premièrement je pense juste pour les notations que tu devrais noter
>>F_n+2, ou F_(n+2), plutot que avec des accolades qui font penser à un
>>ensemble... enfin cela n'a pas d'importance ici.
>
>
> Ben non : c'est de la syntaxe (pseudo-)TeX, les accolades servant à
> grouper un bloc de texte. F_n+2 s'afficherait
> F + 2
> n
> et F_(n+2) deviendrait
> F n + 2)
> (
>
> Seul F_{n+2} fait ce qui faut... ce qui se repère instantanément pour
> qui a fait un peu de TeX.[/color]

Toutes mes excuses, je n'ai jamais fait de tex...


--
albert

[Anonyme]

"albert junior" a écrit dans le
message de news: 4144089B.1020609@hotmail.com...
> Bonjour
>
> premièrement je pense juste pour les notations que tu devrais noter
> F_n+2, ou F_(n+2), plutot que avec des accolades qui font penser à
un
> ensemble... enfin cela n'a pas d'importance ici.

Oui, comme j'ai pu voir, c'est la notation LaTeX

>
> Pour ta première question je ne pense pas que tu ai besoin de
récurrence
> forte, mais par contre il pourrait t'être utile pour commencer ta
> récurence de connaitre la valeur de la différence.
> Cela dit, il y a plus astucieux que la réccurence : tu pars de ta
> différence au rang n+1 (F_n+1)^2 - F_n+2 * F_n et tu essayes en
> remplacant astucieusement d'obtenir une relation avec ta différence
au
> rang n (par exemple, k * [ (F_n)^2 - ... ] , et ensuite tu dis que
c'est
> une suite géometrique dont tu peux donner la formule explicite).

Je vais essayer ca merci

>
> Euh je pense sinon que ton inégalité est fausse, et ne serait ca pas
> plutot :
> F_2n+1/F_2n

Non non j'en suis bien sur, c'est ce qui est marqué sur le DM :

F_{2n+2} F_{2n+1}
________ < phi < __________
F_{2n+1} F_{2n]

Ce qui est plus compatible avec la question suivante, calculer la
partie entière de F_{2n+1}*phi


Fab

[Anonyme]

Dans le message news:414387aa$0$30396$636a15ce@news.free.fr,
Ghostux a écrit:
> Bonsoir,

Bonjour,

> J'ai un petit problème sur un DM de maths, le voici:
> On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
> On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} = F_{n}
> + F_{n-1}
> On me demande des choses que je sais faire , et des choses que je
> ne sais pas faire :
>
> - On me demande de calculer (F_{n})^2 - F_{n+1}*F_{n-1}
> (surement pas recurrence forte, mais je connais juste le principe, je
> ne sais pas comment ca se redige, d'une part ni comment on s'en sert
> d'autre part. )

Récurrence simple ama.
en travaillant l'expression au rang n+1, tu dois pouvoir montrer que
c'est l'opposé de l'expression au rang n.

> - On me demande de comparer phi et ( F_{n+1)*phi + F_{n}) / (
> F_{n}*phi + F_{n-1}) , et je trouve que phi = ( F_{n+1)*phi + F_{n}) /
> ( F_{n}*phi + F_{n-1}), ce qui sera utile pour la question suivante
> surement ...
> - On me demande de montrer que pour tout n >0 ,
> F_{2n+1} / F_{2n+1} Alors j'ai dit que phi = ( F_{n+1)*phi + F_{n}) / ( F_{n}*phi +
> F_{n-1}) , et j'ai posé 2k = n, et j'ai aussi rappelé que F_{2n+1} =
> F_{2n-1} + F_{2n} , mais j'ai l'impression de "tourner en rond" ...
> et je trouve pas... si quelqu'un pouvait m'aider, ce serait sympa .

Pour l'inégalité de gauche:
Tu as déjà montré que:
phi = ( F_{2n+2)*phi + F_{2n+1}) /( F_{2n+1}*phi + F_{2n})
(c'est le résultat précédent, exprimé à l'indice 2n+1).

Mets F_{2n+2} / F_{2n+1} en facteur et montre que la fraction qui reste
est >1
(ça utilisera à un moment le résultat de la 1ere question de ton post)

Pour l'inégalité de droite, même principe.

--
Cordialement,
Bruno

[Anonyme]

"Ghostux" a écrit dans le message de news:
414387aa$0$30396$636a15ce@news.free.fr...
> Bonsoir,
> J'ai un petit problème sur un DM de maths, le voici:
> On me donne phi (le nombre d'or) , phi = (1+sqrt(5))/2
> On définit la suite de Fibonacci par F_0 = 1 F_1 = 1 F_{n+2} =
F_{n}
> + F_{n-1}
> On me demande des choses que je sais faire , et des choses que je
> ne sais pas faire :
>
> - On me demande de calculer (F_{n})^2 - F_{n+1}*F_{n-1}
> (surement pas recurrence forte, mais je connais juste le principe,
je
> ne sais pas comment ca se redige, d'une part ni comment on s'en sert
> d'autre part. )
> - On me demande de comparer phi et ( F_{n+1)*phi + F_{n}) / (
> F_{n}*phi + F_{n-1}) , et je trouve que phi = ( F_{n+1)*phi + F_{n})
/
> ( F_{n}*phi + F_{n-1}), ce qui sera utile pour la question suivante
> surement ...
> - On me demande de montrer que pour tout n >0 ,
> F_{2n+1} / F_{2n+1} < phi < F_{2n+1} / F_{2n}

Oui donc je m'etais bien trompé la aussi, c'est maintenant que je
viens de voir, je suis désolé d'avoir dit non tout à l'heure à albert
junior, j'avais pas vu ce que j'avais ecrit , mais c'est :

F_{2n+2} / F_{2n+1} < phi < F_{2n+1} / F_{2n}

Je ne devrais pas poster après 23h :-s

Fab

[Anonyme]

Bonsoir,
J'arrive enfin (:( ) à la fin de mon DM, j'ai montré tout un tas de
choses, comme par exemple:

1 + sum(F_{2p},p=1..n) = F_{2n+1}
1 + sum(F_{2p+1},p=1..n) = F_{2n+2}


Q2/P2: 1 + sum(F_{m-2k},2k=1..m - 2) = F_{m+1}

Et j'ai aussi montré que pour n >= 1, il existe un seul k >= 2 , tel
que:

Q3/P2 : F_{k} <= n < F_{k+1}

Troisième partie :
"Pour tout entier n appartenant à IN* , il exite un seul k naturel
non nul tel qu'il existe une seule suite
(B_{i})_{1 <= i <= k} d'entiers verifiant :

2 <= B_1 << B_2 << B_3 << ... << B_k et N = F_{B_1} + F_{B_2} + ...
+ F_{B_k}
Une telle écriture du nombre n s'appelle décomposition fibonaccienne.
( F_{n} étant la suite de Fibonacci ).
"
Voila pour "l'intro".
Comme j'avais dit dans mon premier mail, je ne sais pas comment marche
une recurrence forte, je ne sais pas comment la rediger. Si n est
indéfini, comment prouver que ca marche pour tous les n , et en
deduire que ca marche à n+1 ? ... enfin voici la question :
3) Prouver par recurrence sur l'entier N >=1 l'existence de la
décomposition fibonaccienne de n, on pourra utiliser la question 3 de
la partie 2 et une recurrence forte.

Alors j'ai pensé à travailler avec ca : 1 + sum(F_{2p+1},p=1..n) =
F_{2n+2}, en disant que F_{k} = N , et
dire que 2n+2 = k , n = (k -2)/2
N = sum(2p+1,p =1..(k-2)/2) -1 2p+1 = 3 au minimum, ca respecte bien
la condition initialement posée.
Alors le petit problème, c'est je ne n'ai appliqué aucune récurrence
(encore moins "forte"), et de deux, je ne sais pas si c'est bon, il
faudrait poser une condition sur N ... si vous avez une petite piste
(pas trop sombre), je suis prenneur, parce que je vois plus rien.
En attendant, des petits conseils sur la question suivante sont aussi
bienvenus :
4) Montrer l'unicité de la décomposition fibonaccienne ; on pourra
utiliser les questions 2 et 3 de la partie 2.
(je n'ai encore pas reflechi à celle là, mais elle doit etre toute
aussi "subtile" )

Merci beaucoup

Fab

[Anonyme]

Ghostux a écrit:
> Bonsoir,
> J'arrive enfin (:( ) à la fin de mon DM, j'ai montré tout un tas de
> choses, comme par exemple:
>
> 1 + sum(F_{2p},p=1..n) = F_{2n+1}
> 1 + sum(F_{2p+1},p=1..n) = F_{2n+2}
>
>
> Q2/P2: 1 + sum(F_{m-2k},2k=1..m - 2) = F_{m+1}
>
> Et j'ai aussi montré que pour n >= 1, il existe un seul k >= 2 , tel
> que:
>
> Q3/P2 : F_{k}
> Troisième partie :
> "Pour tout entier n appartenant à IN* , il exite un seul k naturel
> non nul tel qu'il existe une seule suite
> (B_{i})_{1
> 2 + F_{B_k}

je dirais plutôt 1 Une telle écriture du nombre n s'appelle décomposition fibonaccienne.
> ( F_{n} étant la suite de Fibonacci ).
> "
> Voila pour "l'intro".
> Comme j'avais dit dans mon premier mail, je ne sais pas comment marche
> une recurrence forte, je ne sais pas comment la rediger. Si n est
> indéfini, comment prouver que ca marche pour tous les n , et en
> deduire que ca marche à n+1 ? ... enfin voici la question :
> 3) Prouver par recurrence sur l'entier N >=1 l'existence de la
> décomposition fibonaccienne de n, on pourra utiliser la question 3 de
> la partie 2 et une recurrence forte
>
> Alors j'ai pensé à travailler avec ca : 1 + sum(F_{2p+1},p=1..n) =
> F_{2n+2}, en disant que F_{k} = N , et
> dire que 2n+2 = k , n = (k -2)/2
> N = sum(2p+1,p =1..(k-2)/2) -1 2p+1 = 3 au minimum, ca respecte bien
> la condition initialement posée.
> Alors le petit problème, c'est je ne n'ai appliqué aucune récurrence
> (encore moins "forte"), et de deux, je ne sais pas si c'est bon, il
> faudrait poser une condition sur N ... si vous avez une petite piste
> (pas trop sombre), je suis prenneur, parce que je vois plus rien.[/color]


Lorse que tu fais une récurrence faible (classique) tu supposes P(n)
vrai pour un n et tu montres que cela implique P(n+1) vrai.
Lors d'une récurrence forte tu supposes que P(k) est vraie pour tout k
== F(K-1)
alors A + F(K) >= F(K+1), et ton inégalité est stricte à droite)

d'après l'hypothèse de récurrence forte, A étant inférieur à n, on peut
décomposer A comme suit : A = F(B1) + F(B2) + ... + F(Bk), et de plus
Bk En attendant, des petits conseils sur la question suivante sont aussi
> bienvenus :
> 4) Montrer l'unicité de la décomposition fibonaccienne ; on pourra
> utiliser les questions 2 et 3 de la partie 2.
> (je n'ai encore pas reflechi à celle là, mais elle doit etre toute
> aussi "subtile" )
>
> Merci beaucoup
>
> Fab
>
>[/color]