Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Enigme de clemclem 12***

Posté par
clemclem Posteur d'énigmes
05-01-05 à 14:33

Bonjour à tous,

Voici la première énigme de clemclem (moi donc ) de cette année 2005 :

Considérons la suite de fibonacci défini par :
F_0=0 et F_1=1
et F_{n+2}=F_{n+1}+F_n

Démontrer que :
\sum_{i=1}^n F_i=F_{n+2}-1

Bonne chance à tous

Clotûre samedi matin.

A plus

Posté par sittingbul (invité)re : Enigme de clemclem 12*** 05-01-05 à 17:03

perdubonjour,
je vais faire un démonstration par récurrence:
Au rang initial 0:
d'après la formule:
F_{n+2}=F_{n+1}+F_n
donc: F_0=F_2-F_1=1-1=0
et la somme
0+F_0=F_2-1=1-1=0
La propriété est donc vrai au rang initial 0.

J'admet donc que la propriété est vraie au rang n
Je vais montrer au rang n+1:
\sum_{i=1}^{n+1} F(i)=F_{n+3}-1
Mais  F_{n+2+1}=F_{n+3}=F_n+2+F_n
Donc la somme :
\sum_{i=1}^{n+1} F(i)=F_{n+3}-1
=F_{n+2} +F_n -1
=\sum_{i=1}^n F(i)+F_n
La propriété est donc héréditaire.
Une propriété étant vrai au rang initaial et étant héréditaire est vraie à tous les rang.

Voilà

Posté par
Ksilver
re : Enigme de clemclem 12*** 05-01-05 à 18:15

gagné

la suite donne 0,1,1,2,3,5 etc...

on resone par recurence :

la proprieter est vrai au rang 1 (1 = F3 -1 )


on suppose qu'il exite un rang n pour laqu'elle la proprieter est vrai.
donc F1 + F2 + F3 +F4...Fn=F(n+2)-1
donc F1+F2+F3...+Fn+F(n+1)=F(n+1)+F(n+2)-1

or F(n+1)+F(n+2) = F(n+3)

donc F1+F2+F3...+Fn+F(n+1)=F(n+3) -1

donc la proprieter est vrai au rang n+1 si elle est vrai au rang n, elle est donc hereditaire et comme elle est vrai au rang 1 elle est vrai pour tous n superieur a 1


Posté par
Lopez
re : Enigme de clemclem 12*** 05-01-05 à 18:23

gagnéBonjour,
F_{n+2}=F_{n+1} + F_n
F_{n+1}=F_n + F_{n-1}
F_n =F_{n-1} + F_{n-2}
   -     -      -
   -     -      -
   -     -      -
F_3=F_2 + F_1
F_2=F_1 + F_0

On fait la somme membre à membre et on obtient :

F_{n+2} + \sum_{i=2}^{n+1}F_i = \sum_{i=2}^{n+1}F_i + \sum_{i=1}^{n}F_i + F_1 + F_0

En supprimant la somme identique des deux côtés de l'égalité il nous reste :

F_{n+2} = \sum_{i=1}^{n}F_i + 1 + 0
d'où \sum_{i=1}^{n}F_i = F_{n+2} - 1

cqfd

Posté par jetset (invité)re : Enigme de clemclem 12*** 05-01-05 à 18:35

perduOn procède par récurrence:
Pour i=0, la propriété est vérifiée car:
F2=F0+F1= 1

On suppose la pté vérifiée pour le rang p:
somme (1 à p) Fp = Fp+2 - 1

Or, somme (1 à p+1) Fp = somme (1 à p) Fp + Fp+1 = Fp+2 - 1 + Fp+1 = Fp+3 - 1
Donc somme (1 à p+1) Fp = Fp+3 - 1. La propriété est donc bien vérifiée pour le rang p+1

La propriété "somme (1 à n) Fn = Fn+2 - 1" est donc bien valable quelque soit l'entier naturel n

Posté par gilbert (invité)re : Enigme de clemclem 12*** 05-01-05 à 18:42

gagnéOn écrit les relations
Fn+2= Fn+1+ Fn
Fn+1= Fn+ Fn-1
Fn= Fn-1+ Fn-2
Fn-1= Fn-2+ Fn-3
...
...
F2= F1+ F0

Si je fais la somme de ces égalités , la plupart des termes de part et d'autre du signe = se simplifient et on obtient :
Fn+2= F1+ 0n Fi
F1=1 et  0n Fi = 1n Fi car F0= 0.
Donc 1n Fi = Fn+2- 1





Posté par
nicodelafac
re : Enigme de clemclem 12*** 05-01-05 à 18:45

perduPar récurrence, c'est assez facile à montrer :
Nous avons F1=1 et 11F1=1
L'égalité est donc vérifiée pour n=1

Supposons l'égalité vérifiée pour n. Montrons qu'elle est vérifiée pour n+1

Nous avons n+11Fi= n1Fi + Fn+1
D'après notre hypothèse, nous avons alors :
n+11Fi=Fn+2-1+Fn+1 et par définition de la suite : Fn+2+Fn+1=Fn+3
Ainsi n+11Fi=Fn+3-1

Nous avons donc montré que l'égalité :
  - Est vérifiée pour n=1 ;
  - Est vérifiée pour n+1 si elle l'est pour n.

On en conclu alors que n1Fi=Fn+2-1 pour tout n1

cqfd

Posté par Fabien (invité)Récurrence 05-01-05 à 19:02

Par récurrence:

Pour n=1, la propriété est vérifiée, chaque terme vaut 1.

Supposons la propriété vraie à un rang n, est-elle vraie au rang suivant: n+1 ?

\sum_{i=1}^n F_i = F_{n+2}-1 est vraie !
Est ce que \sum_{i=1}^{n+1} F_i = F_{n+3}-1 est vrai !

D'après définition:
F_{n+3} = F_{n+2} + F_{n+1}
Donc
F_{n+3} - 1 = F_{n+2} + F_{n+1} - 1

Mais F_{n+2} - 1 = \sum_{i=1}^n F_i

Donc F_{n+3} - 1 = \sum_{i=1}^n F_i + F_{n+1}

ET donc F_{n+3} - 1 = \sum_{i=1}^{n+1} F_i

Conclusion habituelle d'une récurrence...

Et donc \sum_{i=1}^n F_i = F_{n+2}-1

Posté par DivXworld (invité)re : Enigme de clemclem 12*** 05-01-05 à 20:54

gagnébon alors c'est parti pour la récurrence:

d'abord le blabla: on pose P(n) la propriété a démontrer (désolé je sais pas encoretrop me servir du latex et j'ai pas vraiment le temps)

_on vérifit pour n=1
F1=1
F1+2-1
=F2+F1-1
=F1+F0+F1-1
=1
P(1) est vraie

_on suppose P(n) vrai pour une valeur de n
i.e. somme de i=1 a n
Fi=Fn+2-1


somme de i=1 a n+1
Fi
=Fi(de 1 a n)+Fn+1
=Fn+2-1+Fn+1
=Fn+3-1

donc P(n+1) est vraie

_P(1) est vraie
n* P(n)P(n+1)

n* P(n) est vraie

voila voila

Posté par
manpower
re : Enigme de clemclem 12*** 05-01-05 à 23:38

gagnéPar récurrence !
Hypothèse : (Hn) : \sum_{i=1}^n F_i=F_{n+2}-1

(H1) est vraie : F_1 = F_3 - 1

Supposons (Hn) vraie pour un entier n1
et montrons que (Hn+1) est vraie :

\sum_{i=1}^n+1 F_i=\sum_{i=1}^n F_i + F_{n+1}
\sum_{i=1}^n+1 F_i=F_{n+2} - 1 + F_{n+1}  avec (Hn)
\sum_{i=1}^n+1 F_i=F_{n+3} - 1   avec F_{n+3} = F_{n+2} + F_{n+1}

(Hn+1) est vraie

Conclusion : Pour tout entier n1, (Hn) est vraie.

Posté par levrainico (invité)enigme de clemclem 06-01-05 à 03:16

gagnébien le bonjour, je suis un petit nouveau
je connais le site depuis un petit moment, mais je n'ai jamais pris le temps d'envoyer des messages

ben mon premier sera la reponse a cette enigme.   j'avais preparé ma reponse sous word, mais quand j'ai fait le copie collé, ca n'afficahait pas les equatiosn
j'ai bienessaye avec les latex, trop galere

donc j'ai juste fait un imprim ecran  ->   desole Webmaster..

A+
levrainico

enigme de clemclem

Posté par pietro (invité)re : Enigme de clemclem 12*** 06-01-05 à 08:21

Calculons quelques premiers termes.
F0 = 0
F1 = 1
F2 = F1 + F0 = 2
F3 = F2 + F1 = 3
F4 = F3 + F2 = 5
F5 = F4 + F3 = 8

Démonstration par récurrence de la propriété :
1) Montrons qu'elle est vraie  pour les premières valeurs de n.
   a) n=1     \sum_{i=1}^1 Fi =? F3 - 1
      F1 = 2 - 1 = 1 oui
   b) n=2     F1 + F2 =? F4 - 1
      1 + 1 = 2 =? 3 - 1 oui
   c) n=3    F1 + F2 + F3 =? F5 - 1
      1 + 1 + 2 =? 5 - 1
      4 = 5 - 1 oui
2) Supposons que la propriété soit vraie pour i allant de 1 à k-1, et montrons qu'elle est alors vraie pour i allant de   1 à k.
On a donc \sum_{i=1}^{k-1} Fi = Fk+1 - 1
d'où \sum_{i=1}^k Fi = (Fk+1 - 1) + Fk
  = (Fk+1 + Fk) - 1
  = Fk+2 - 1
3) La propriété étant vraie pur n=3 est donc vraie pour n=4. Etant vraie pour n=4 elle est donc vraie pour n=5,......etc Elle est donc vraie pour toute valeur de n.


Enigme de clemclem 12

Posté par Al1 (invité)re : Enigme de clemclem 12*** 06-01-05 à 14:45

Bon, je propose une récurrence...

F3=2
Posons S(n) = somme des F(i) de 1 à i
S(1)=1, F(3)-1=1, c'est bon... la première étape de ma récurrence est démontrée...

on suppose que S(n)=F(n+2)-1
S(n+1)=S(n)+F(n+1)=F(n+2)+(Fn+3)-1=F(n+4)-1

La propriété est conservée

CQFD

Posté par
Nofutur2
re : Enigme de clemclem 12*** 06-01-05 à 15:00

gagnéF_{n+2} = F_{n+1}+ F_{n}
F_{n+1} = F_{n}+ F_{n-1}
......
F_{2} = F_{1}+ F_{0}

En ajoutant membre à membre et en simplifiant, on obtient  :
\sum_{i=0}^n F_i = F_{n+2} - F_{1}
Comme F_{1} = 1 et  F_{0} = 0   on peut écrire :
\sum_{i=1}^n F_i = F_{n+2} - 1

Posté par matt- (invité)re : Enigme de clemclem 12*** 06-01-05 à 17:37

gagnéOn démontre çà par récurrence sur N.
Au rang 1 : Somme de 1 à 1 des F(i) = F(1) = 1 = 2-1 = F(2) - 1 donc la propriété est vérifiée.
Soit n un entier naturel. On suppose la propriété vraie au rang n. Au rang n+1, on a :
  Somme de 1 à n+1 des F(i) = (somme de 1 à n des Fi) + F(n+1) = F(n+2) - 1 + F(n+1) (hyp. de récurrence) = F(n+3) - 1, ce qui achève le raisonnement par réccurence.
QED !
PS : c'est pas vraiment une énigme :p

Posté par julien12ever (invité)re : Enigme de clemclem 12*** 06-01-05 à 19:45

gagnéutilisons une méthode de récurrence:
pour n=1:
\sum_{i=1}^1 F_i = F_1 = 1 = 2-1 = F_3 -1
Hérédité: on suppose que pour tout n de \mathbb{N} on a:

           \sum_{i=1}^n F_i=F_{n+2}-1      

Cette relation est-elle vrai au rang n+1?

Pour tout n de \mathbb{N} :
\sum_{i=1}^{n+1} F_i = \sum_{i=1}^{n} F_i + F_{n+1}
\sum_{i=1}^{n+1} F_i = F_{n+2} -1 + F_{n+1}

or F_n + F_{n+1} = F_{n+2}
  (par définition de la suite)
donc F_{n+2} + F_{n+1} = F_{n+3}

Ainsi \sum_{i=1}^{n+1} F_i = F_{n+3} -1

donc la relation est vrai au rang n+1 lorsqu'on la suppose vraie au rang n or elle est vrai pour n=1 donc elle est vrai pour tout n


voila, je te remerci pour le smiley

Posté par
franz
re : Enigme de clemclem 12*** 06-01-05 à 20:02

gagnéSoit S_n = \Bigsum_{i=1}^n F_i

\array{ccl$ 2 S_n = 2\,\Bigsum_{i=1}^n F_i & = & ( F_n + \Bigsum_{i=0}^{n-1} F_i - F_0) + \Bigsum_{i=1}^{n} F_i \\ & = & F_n - F_0 + \Bigsum_{i=1}^{n} (F_i+F_{i-1}) \\ & = & F_n - F_0 + \Bigsum_{i=1}^{n} F_{i+1} \\ & = & F_n - F_0 + \Bigsum_{i=2}^{n+1} F_{i}\\ & = & F_n - F_0 + ( F_{n+1}-F_1 + \Bigsum_{i=1}^{n} F_{i} ) \\ & = & (F_n + F_{n+1}) - (F_1 + F_0) + \Bigsum_{i=1}^{n} F_{i} \\ 2 S_n & = & F_{n+2} - F_2 + S_n

Comme F_2 = F_0 + F_1 = 1 + 0 =1 en retranchant S_n à chacun des termes de l'égalité précédente on arrive au résultat

                 \fbox{\large \red S_n = \Bigsum_{i=1}^n F_i = F_{n+2} - 1 }


Posté par MPSI-1 (invité)re : Enigme de clemclem 12*** 06-01-05 à 20:45

gagnéutilisons une méthode de récurrence:
pour n=1:
F_1 = 1 = F_3 -1

supposons pour tout entier naturel non nul n:      \sum_{i=1}^n F_i=F_{n+2}-1      

Pour tout entier naturel non nul n:
\sum_{i=1}^{n+1} F_i = F_{n+2} -1+F_{n+1}                                                
or F_{n+2} + F_{n+1} = F_{n+3} d'après l'énoncé

d'où \sum_{i=1}^{n+1} F_i = F_{n+3} -1

la récurrence marche donc voila je l'ai démontré

Posté par ametist (invité)encore si j ai bonne mémoire des récurrences 06-01-05 à 23:55

perduVérifions que çà marche pour n=2
F1+F2=1+1=2
F4-1=3-1=2 donc çà marche F1+F2=F4-1
supposons que c'est vrai au rang n
F1+F2+...+Fn=Fn+2 - 1
F1+F2+...+Fn+ Fn+1 + Fn+2 =Fn+1 + 2*Fn+2 -1
                          =Fn+3 + Fn+2 - 1
donc
F1+F2+...+Fn+ Fn+1 = Fn+3 - 1
donc vrai au rang n+1
donc l'égalité est vraie par récurrence

Posté par mickachef (invité)vive la récurrence!! 07-01-05 à 13:38

gagnévoila on se propose de démontrer par récurrence Pn, la propriété suivante :
(Somme de i=1 à n de Fi = F(n+2) -1 ) kelke soi 'n' non nul de N.
initialisation
par hypothese on sait que F(1) = 1; F(0)=0          et  F(n+2)= F(n+1)+Fn donc F(2)= 1+0=1 et F(3)= 1+1=2
Or, Somme de i=1 à 1 de Fi = F(1)= F(1+2) -1=2-1 =1
on retouve bien alor F(1) = 1 et P1 est vérifiée et donc Pn est initialisée!!

Hérédité
Supposons Pn vraie pr un entier naturel non nul , Pn+1 est vraie?? c a dire, Somme de i=1 à n+1 de Fi = F(n+3) -1 ??????

par hypothese
F(n+2)= F(n+1)+Fn
ce ki ékivo a
F(n+3)=F(n+2)+F(n+1)

Or, Somme de i=1 à n+1 de Fi = (Somme de i=1 à n de Fi) + F(n+1) = F(n+2)-1+ F(n+1)
(car d'apres lhypothese de récurrence, (Somme de i=1 à n de Fi = F(n+2) -1 ))
ainsi , P(n+1)= F(n+2)+F(n+1) -1 = F(n+3)- 1  : CQFD

Pn est héréditaire et initialisée elle est donc vraie kelke soit n non nul dans N!!
oléééééééé

Posté par daniel12345 (invité)re : Enigme de clemclem 12*** 07-01-05 à 16:07


   Démonstration par récurrence

   1) la formule (1)  \sum_{i=1}^n f(i)= F_{n+2} -1 doit être vraie
       pour i=1  \sum_{i=1}^1 f(i) =1        et   F_3-1=2-1 = 1      ok

       pour i=2  \sum_{i=1}^2 f(i) =1+1=2  et   F_4-1=3-1 = 2      ok


    2) on suppose (2)  \sum_{i=1}^n f(i)= F_{n+2} -1 vrai au rang n.
        Il faut maintenant  démontrer qu'elle est vraie au rang n+1

          Soit  F_0+F_1+...+F_n+F_{n+1}=F_{n+3}-1   

             On rajoute F_{n+1} a (2) d'ou

                  F_0+F_1+...+F_n+F_{n+1}=F_{n+2}-1 + F_{n+1}  

        On obtient donc : F_{n+3}-1= F_{n+2}-1 + F_{n+1}

           Finalement F_{n+3}= F_{n+2} + F_{n+1} est vrai puisque c'est la suite de fibonacci .
    
         Donc la formule (1) est démontrée pour tout n.










    







Posté par CastorFantome (invité)re : Enigme de clemclem 12*** 07-01-05 à 17:53

gagnéJe propose d edémontrer par récurrence.
Je ne suis toujours pas sur de la syntaxe Latex vu que je n'arrive pas à accéder a l'aide La j'ai recuperer les smiley c'est déja un bon point mais je n'ai pas non plus les symbole donc je sens que je vaiis m'amuser

Donc verifions au rang n=1 :

\sum_{i=1}^{n=1} F_{i}=F_3-1

Or F_3=F_2+F_1=F_1+F_0+F_1

donc \sum_{i=1}^{n=1} F_{i}=F_3-1=F_1+F_0+F_1-1=F_1

Donc cela est vrai pour n=1

Verifins si lorsque c'est vrai à un rang n , c'est aussi vrai au rang n+1
Posons :
S_n=\sum_{i=1}^{n} F_{i}
Donc S_{n+1}=\sum_{i=1}^{n+1} F_{i}=S_n+F_{n+1}

S_{n+1}=S_n+F_{n+1}=F_{n+2}-1+F_{n+1}
Or Fn+3=Fn+2+Fn+1

Donc S_{n+1}=F_{n+3}-1=F_{(n+1)+2}-1
Donc l'hypothèse est vrai au rang n+1

Quelque soit n, cela est vrai
S_{n}=\sum_{i=1}^{n} F_{i}=F_{n+2}-1

Posté par mani (invité)re : Enigme de clemclem 12*** 08-01-05 à 02:15

F0=0
F1=1
F2=F1+0
F3=F2+F1
F4=F3+F2
F5=F4+F3
.
.
.
Fn-2=Fn-3+Fn-4
Fn-1=Fn-2+Fn-3
Fn=Fn-1+Fn-2
si
Sn=F1+F2+...+Fn

nous avons donc:
Sn=1+2(F1+F2+...+Fn-2)+Fn-1
Sn=1+2Sn-2+Fn-1
on sait que:
Sn-2=Sn-Fn-1-Fn
donc
Sn=1+2(Sn-Fn-1-Fn)+Fn-1
ou
Sn=Fn-1+2Fn-1
Sn=(Fn-1+Fn)+(Fn)-1
Sn=(Fn+1)+(Fn)-1
Sn=(Fn+2)-1

voila!

Posté par lucas640 (invité)re : Enigme de clemclem 12*** 08-01-05 à 11:55

comment on fait

Posté par
clemclem Posteur d'énigmes
re : Enigme de clemclem 12*** 08-01-05 à 13:48

Bravo à tous,

Deux méthodes ont été utilisés : la récurrence et l'addition membre à membre.
Il en existait une autre , celle que j'ai utilisé pour prouver ce résultat ( beaucoup plus longue ) : utiliser la formule de la suite de Fibonacci(F_n=\frac{1}{5}(\phi^n-\bar{\phi}^n)) puis faire joujou () avec le nombre d'or et son conjugué.

A plus pour de prochaines aventures

Posté par
franz
re : Enigme de clemclem 12*** 08-01-05 à 18:04

gagné\large F_n=\frac{1}{\sqrt 5}(\phi^n-\bar{\phi}^n) si je puis me permettre.

Merci pour cette énigme.

Posté par
clemclem Posteur d'énigmes
re : Enigme de clemclem 12*** 08-01-05 à 18:24

Effectivement,petit oubli de ma part

Heureusement que tu veilles franz

Posté par jetset (invité)re : Enigme de clemclem 12*** 08-01-05 à 21:00

perduEuh.... Quelle est la raison de mon poisson?

Posté par
clemclem Posteur d'énigmes
re : Enigme de clemclem 12*** 09-01-05 à 13:17

Bonjour jetset,

Le problème de ta démonstration est qu'elle démarre au rang 0.Alors qu'il est clairement dit dans l'énoncé que la somme commence au rang 1.

Il s'agit donc d'une erreur d'initialisation de ta récurrence.

Voilà tout

A plus

Posté par Emma (invité)re : Enigme de clemclem 12*** 09-01-05 à 13:35

Salut jetset

Le raisonnement par récurrence est primordial, et pourtant parfois difficile à rédiger.
Ayant remarqué quelques problèmes dans ta rédaction, je me permets donc de compléter la réponse de clemclem...

D'une part, ton initialisation n'est pas bonne :
lorsque l'on demande de démontrer que \sum_{i=1}^n%20F_i=F_{n+2}-1, la récurrence doit se faire sur n appartenant à * et pas sur i appartenant à

Mais d'autre part, il y a un problème dans la seconde étape de ta démonstration :
lorsque tu démontres le caractère héréditaire, tu écris
----
On suppose la pté vérifiée pour le rang p:
somme (1 à p) Fp = Fp+2 -
----

Mais cela n'a pas de sens : p est à la fois la borne de ta somme et l'indice qui semble varier...
C'est comme si tu avais écrit :
\sum_{p=1}^{p=p}\;\;F_p\;\;=\;\;F_{p+2}

Alors que si tu supposes la propriété vraie au rang p, tu supposes que \sum_{i=1}^{i=p}\;\;F_i\;\;=\;\;F_{p+2}

@+
Emma

Posté par jetset (invité)re : Enigme de clemclem 12*** 09-01-05 à 18:36

perduok ok. N'en jetez plus. Ce n'était que de l'étourderie. Le raisonnement était valable quand même... J'essaierai de faire plus attention la prochaine fois.

Posté par
nicodelafac
re : Enigme de clemclem 12*** 11-01-05 à 14:21

perduHello Clemclem!

Pourrais tu me dire ce qu'il y a de faux dans ma réponse?

Posté par
clemclem Posteur d'énigmes
re : Enigme de clemclem 12*** 11-01-05 à 18:28

Bonjour nicodelafac,

La aussi je trouve un problème dans ta démonstration au niveau de l'initialisation de la récurrence.
Tu calcules \sum_{i=1}^1%20F_i mais tu ne me prouves pas que \sum_{i=1}^1%20F_i = F_3 -1

Voilà

A plus

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 21:44:37.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !