Forum de mathématiques - Bibm@th.net

pikachu

Membre

Inscription : 04-09-2015

Messages : 9

Démonstration par récurrence

Bonjour,

En considérant la suite (Un) telle que : U0=0n et Un+1  = 3Un - 2n + 3

Je dois montrer que:
[tex]\forall n\in \mathbb{N}\\
Un\ge n[/tex]

J 'ai fait l'initialisation et vérifier P0 mais je bloque sur l'hérédité.

Merci d'avance pour votre aide.

ymagnyma

Membre

Inscription : 06-10-2012

Messages : 412

Re : Démonstration par récurrence

Bonsoir Pikachu.

Pour cette question tu dois systématiquement commencer par donner un nom à la propriété que tu cherches à prouver.
Appelons P la propriété que tu veux prouver. Puisque cette propriété dépend de l'entier n, on la notera [tex]P(n)[/tex].

Ainsi, on commence par écrire :"Soit [tex]P(n)[/tex] la propriété "[tex]U_n>=n[/tex]"."

Ce qu'on va faire c'est prouver que, pour tout entier n, [tex]P(n)[/tex] est vraie.

Tu écris que tu as prouvé que [tex]P(0)[/tex] est vraie. On appelle en effet cette étape l'initialisation. Tu as donc prouvé que [tex]U_0>=0[/tex].

Tu bloques sur l'hérédité. Qu'est-ce que l'hérédité ?
Soit un entier k fixé. on se pose la question suivante : si [tex]P(k)[/tex] est vraie, soit encore, si la propriété au rang k est vraie, soit encore, si [tex]U_k>=k[/tex], est ce que, sous cette hypothèse, [tex]P(k+1)[/tex] est également vraie, soit encore, est-ce que la propriété est encore vraie au rang k+1.

Mais au fait, c'est quoi [tex]P(k+1)[/tex] ?

peux-tu déjà répondre à cette question.

Dernière modification par ymagnyma (11-09-2015 18:47:01)

pikachu

Membre

Inscription : 04-09-2015

Messages : 9

Re : Démonstration par récurrence

Bonsoir Ymagnyma,

P(k+1)= 3Uk-2k+3 
mais je bloque sur comment prouver que ceci est supérieur ou égal à k+1

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

Bonjour,

Ton [tex]U_0[/tex] me gêne : [tex]U_0= 0n[/tex] tu veux dire [tex]U_0 = 0[/tex] ?
Mais après tout, on s'en moque un peu, puisque c'est l'hérédité qui coince...
Donc pour l'hérédité, c'est plus simple que tout ce à quoi tu as probablement pensé.
1. Tu supposes vrai que [tex] n \in \mathbb{N},\; U_n\geq n[/tex]
2. Tu veux montrer que dans ce cas [tex]U_{n+1}\geq n+1[/tex]
On te dit que
[tex]U_{n+1}=3U_n-2n+3[/tex]
si, dans cette égalité, tu remplaces [tex]U_n[/tex] par n, compare donc alors
[tex]U_{n+1}[/tex] et [tex]3n-2n+3[/tex]

@+

[EDIT] Je découvre la réponse d'Ymagnima...

Dernière modification par yoshi (11-09-2015 18:34:27)

ymagnyma

Membre

Inscription : 06-10-2012

Messages : 412

Re : Démonstration par récurrence

Ok, Pikachu, c'est là que tu te trompes, tu confonds le nombre [tex]U_{k+1}[/tex] et la propriété [tex]P(k+1)[/tex].

Tu as [tex]P(0)[/tex] : "[tex]U_0 >=0[/tex]" ;
          [tex]P(k)[/tex] : "[tex]U_k >= k[/tex]"

Alors, [tex]P(k+1)[/tex], c'est quoi ?

pikachu

Membre

Inscription : 04-09-2015

Messages : 9

Re : Démonstration par récurrence

Ymagnyma,

P(k+1) est donc la proposition telle que Uk+1 >= k+1 soit telle que 3Uk-2k+3

Yoshi,
Excuse moi mais je ne comprends ce que tu me demandes de faire

Terces

Membre

Inscription : 16-07-2015

Messages : 466

Re : Démonstration par récurrence

Salut,
Tu as fait l’initialisation.
Maintenant tu peux donc dire que pour un certain n appartenant à N on a:
Un >= n

Et tu cherches à montrer que Un+1 >= n+1  ainsi ta propriété est vérifié pour le rang n+1 donc c'est démontré.

Tu pars sur le fait que:

Un >= n
Tu as le droit de multiplier par 3 :)
3Un >= 3n d'après l'hypothèse de récurrence.
puis tu continues.

N'oublies pas ton objectif:
Un+1 >= n+1

Bon j'espère que c'est juste et que si tel est le cas que c'est assez bien formulé (bien sure ce n'est qu'un indice, la rédaction n'est ici pas du tout fini).

Dernière modification par Terces (11-09-2015 19:30:09)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

Re,

Excuse moi mais je ne comprends ce que tu me demandes de faire

Je te dis de comparer
[tex]U_{n+1}[/tex] et [tex]3n-2n+3[/tex]
Comparer signifie mettre [tex]>[/tex], [tex]<[/tex], [tex]\geq[/tex], [tex]\leq[/tex] ou [tex]=[/tex] entre les deux.
Je vais te mettre sur la voie :
quand dans [tex]3U_n-2n+3[/tex] tu remplaces [tex]U_n[/tex] par n, minores-tu ou majores-tu [tex]3U_n-2n+3[/tex] sachant que [tex]U_n\geq n[/tex] ?

Après ce n'est plus qu'une manipulation élémentaire d'inégalités...

@+

ymagnyma

Membre

Inscription : 06-10-2012

Messages : 412

Re : Démonstration par récurrence

Bonjour,

je repars du post#6
Tu supposes que [tex]u_k>=k[/tex] et tu veux montrer que [tex]u_{k+1}>=k+1[/tex]. En écrivant ça, tu sais où tu veux aller :

montrons que si [tex]u_k>=k[/tex] alors [tex]3u_k-2k+3>=k+1[/tex].

Là, Yoshi, (Post#4 et 8), et Terces t'indiquent comment procéder c'est à dire comment passer de [tex]u_k[/tex] à [tex]u_{k+1}[/tex] par ce qu'on appelle des opérations élémentaires, à savoir additions, multiplications ...

Exemple. Soit [tex]v_{k+1}=0.8v_k-5[/tex] et [tex]v_0=3[/tex]

Montrons que si [tex]v_k>-25[/tex] alors [tex]v_{k+1}>-25[/tex]. Je montre donc uniquement l'hérédité de la propriété [tex]P(n)[/tex] : "[tex]v_n>-25[/tex]".

Puisque [tex]v_k>-25[/tex] alors [tex]0.8 v_k > 0.8*(-25)[/tex] soit [tex]0.8 v_k > -20[/tex] puis [tex]0.8v_k -5 >-20-5[/tex] soit [tex]u_{k+1}>-25[/tex].
Cette dernière inégalité c'est précisément [tex]P(k+1)[/tex].

On vient de passer de [tex]P(k)[/tex] à [tex] P(k+1)[/tex].

A toi de jouer.

pikachu

Membre

Inscription : 04-09-2015

Messages : 9

Re : Démonstration par récurrence

Ok,

[tex]Uk\ge k \\
alors \ 3Uk\ge 3k \\
puis \ 3Uk-2k\ge 3k-2k \\
soit \ 3Uk\ge k \\\
et \ 3Uk-2k+3\ge k+3[/tex]

Mais comment revenir à k+1

Ps : oui je sais j'en demande beaucoup désolé j'ai du mal à capter tout ça ...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

Re,

Mais comment revenir à k+1 ?

Bin, en comparant k+3 et k+1...

Cela dit, l'énoncé utilise n, alors utilise n et pas k...

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

@Tercès :
1. ça t'arrive de lire ce que les autres écrivent avant toi ?
2. ça

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

@Tercès :
1. ça t'arrive de lire ce que les autres écrivent avant toi ? avant et après avoir posté ?
2. ça te sert à quoi de reprendre intégralement les posts précédents ? Ça ajoute quoi ?

Là, c'est le modo qui cause...

@+

Terces

Membre

Inscription : 16-07-2015

Messages : 466

Re : Démonstration par récurrence

Désolé yoshi, il y a un mal entendu!

Regarde tu as écrit ton post 35 sec avant le miens(enfin je viens de le supprimer mais je penses que tu me crois), quand j'ai commencé à écrire, tu n'avais donc pas posté ton post que je n'ai donc pas vu...

Dernière modification par Terces (12-09-2015 14:25:10)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Démonstration par récurrence

Re,

Regarde tu as écrit ton post 35 sec

Niet, s !

35 sec avant le mien

C'est bien pourquoi, j'ai écrit "avant et après"...
Ça m'arrive aussi, et dans ce cas, par courtoisie, j'édite mon post pour signaler que je n'avais pas vu ! ;-)

@+

ymagnyma

Membre

Inscription : 06-10-2012

Messages : 412

Re : Démonstration par récurrence

Bonsoir, ce que tu as fait au post #10 est très bien, tout est bon, et en effet, comme te le dit Yoshi, il ne te reste plus qu'à comparer [tex]k+3[/tex] et [tex]k+1[/tex] pour conclure que si [tex]P(k)[/tex] est vraie, ben [tex]P(k+1)[/tex] est vraie aussi.

Je t'ai proposé de fixer un entier que j'ai nommé k pour le distinguer de la notation, "pour tout n".

Dans la conclusion, troisième étape de la récurrence, je reprends la notation du départ, à savoir la notation [tex]P(n)[/tex].
[tex]P(n)[/tex] est vraie pour [tex]n=0[/tex], héréditaire puisqu'à [tex]k[/tex] fixé, [tex]P(k)[/tex] implique [tex]P(k+1)[/tex], donc, d'après l'axiome de récurrence, vraie pour tout entier [tex]n[/tex].

Dernière modification par ymagnyma (12-09-2015 17:35:16)

pikachu

Membre

Inscription : 04-09-2015

Messages : 9

Re : Démonstration par récurrence

Merci beaucoup Yoshi et Ymagnyma,
J'ai compris : on dit que
Or : [tex]3Uk-2k+3\ge k+3\ge k+1\\\
Donc : Uk+1\ge k+1 \\et \ Uk+1\ est \ vraie[/tex]

On peut donc conclure et dire que que [tex]\forall n\in\mathbb{N}\\\ Un\ge n+1[/tex]

Merci de votre aide à tous !

ymagnyma

Membre

Inscription : 06-10-2012

Messages : 412

Re : Démonstration par récurrence

Oui, très bien mais attention, ce n'est pas [tex]u_{k+1}[/tex] qui est vraie ; [tex]u_{k+1}[/tex], c'est un nombre, pas une proposition ; mais en revanche, c'est [tex]P(k+1)[/tex] qui est vraie.
De rien, au plaisir, et bravo.