Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale SuitesTopics traitant de Suites [tout]Lister tous les topics de mathématiques

1 2 +

Posté par
alb12re : Raisonnement par récurrence 28-09-18 à 22:42

Soit P une propriete definie sur N
Si:
1/ P(0) est vraie
2/ pour tout entier n, P(n) implique P(n+1)
alors pour tout entier n, P(n) est vraie.

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 22:45

Déjà, j'aimerais que l'on parte de l'implication :

\forall n\in \mathbb{N}, \quad P(n)\implies P(n+1)

On sait qu'une erreur courante est de dire :

On suppose que  \forall n\in \mathbb{N}, \quad P(n) et on montre P(n+1)

Dans les ouvrages, cette faute est considérée comme gravissime. En effet il n'y a plus rien à montrer

Maintenant si on s'intéresse à la proposition suivante :
Supposons qu'il existe un entier n pour lequel P(n) est vraie.  \iff \exists n\in \mathbb{N},\;P(n)

Or \bigg(\forall n\in \mathbb{N},\;P(n) \bigg)\implies \bigg(\exists n\in \mathbb{N},\;P(n) \bigg), déjà il y a un truc qui cloche


De plus si on dit : \exists n\in \mathbb{N},\;P(n) ,  montrer que P(n+1) est vraie, permet seulement de conclure ceci :


\exists n\in \mathbb{N}, \quad P(n)\implies P(n+1) et la chaîne d'implication comporte des maillons manquants.
_______________________________________________________________________________

Lorsque l'on dit que : Soit n quelconque et on suppose P(n) vraie.

n est un représentant de toutes les entiers, en montrant P(n+1),  c'est équivalent à :

n=0, on suppose P(0),on ne sait rien sur les autres, on montre P(1)
....
n=5, on suppose P(5) et on ne sait rien sur les autes, on montre P(6)
....
n=p, on suppose P(p), on ne sait rien sur les autres , on montre P(p+1)

et ceci pour tout les entiers.


Ce qui est différent de la formulation "Supposons qu'il existe un entier n pour lequel P(n) est vraie."


J'ai essayé, je ne suis pas logicien, et évidemment je pense qu'il y a beaucoup mieux comme argumentation. Je vais tenter de faire mieux mais il me faut plus de temps

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 22:50

alb12

La question porte sur la bonne formulation lorsque l'on montre l'hérédité:



Supposons qu'il existe un entier n pour lequel P(n) est vraie

ou

Soit n quelconque et on suppose P(n) vraie.

Posté par
alb12re : Raisonnement par récurrence 28-09-18 à 22:53

ni l'une ni l'autre à mon avis.

Posté par
carpediemre : Raisonnement par récurrence 28-09-18 à 22:55

merci ...

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 22:59

alb12 merci mais la réponse, est-elle dans ton document?

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 23:00

carpediem, j'ai l'impression que tu es d'accord avec tout le monde sauf avec moi

Posté par
alb12re : Raisonnement par récurrence 28-09-18 à 23:05

A mediter:
2/ pour tout entier n, 2n impair implique 2(n+1) impair
cette assertion est-elle vraie ou fausse ?

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 23:16

tu ne vas pas me faire le coup de carpediem quand même!!

Si tu veux me dire qu'on peut avoir

\forall n \in \mathbb{N},\; \neg P(n) de vraie et \forall n \in \mathbb{N},\; P(n)\implies P(n+1) de vraie, ce n'est pas la question!!!

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 23:19

elle est vraie ton implication

alors quelle est ta conclusion???

Posté par
alb12re : Raisonnement par récurrence 28-09-18 à 23:24

il ne faut pas abuser des symboles, on doit pouvoir s'adresser à un eleve en langage courant. Au fait quelle est la question ?

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 23:27

est-tu en train de me dire qu'il suffit qu'il existe un n où la propriété se transmet au rang n+1, pour conclure qu'elle se transmet à n'importe quel rang????

Si c'est ça, il va falloir que je creuse davantagele sujet .

Posté par
mousse42re : Raisonnement par récurrence 28-09-18 à 23:28

alb12 Voici ma question

mousse42 @ 28-09-2018 à 22:50

alb12

La question porte sur la bonne formulation lorsque l'on montre l'hérédité:



Supposons qu'il existe un entier n pour lequel P(n) est vraie

ou

Soit n quelconque et on suppose P(n) vraie.

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 01:39

alb12 Je pense que tu as raison, les deux ne conviennent pas.


On veut montrer que P(n) : 2^n\ge n^2

Je commence par l'hérédité .

Soit n\in \mathbb{N} et P(n) vraie

2^{n+1}\ge (n+1)^2\iff 2^n+2^n\ge n^2+2n+1\iff 2^n\ge 2n+1

or 2^n\ge n^2 et donc [n^2\ge 2n+1]\implies [2^n\ge 2n+1]

n^2\ge 2n+1\iff n^2-2n-1\ge 0 ce qui donne S=\big\{1-\sqrt{2},1+\sqrt{2}\big\} donc P(n+1) est vraie pour n\ge 3

On a donc montré que pour tout n\ge 3, \; P(n)\implies P(n+1)

P(3)=8\ge 9 donc P(3) est faux
P(4)=16\ge 16 donc P(4) est vraie

Ainsi \forall n\ge 4 ,\quad 2^n\ge n^2


Donc la meilleur formulation (à mon avis) pour l'hérédité c'est :

Soit n\in \mathbb{N} et P(n) vraie


et surtout pas de quantificateur

Posté par
carpediemre : Raisonnement par récurrence 29-09-18 à 07:51

ha ben enfin !!!

alb12 a proposé un exemple du même type que moi !!!

je dirai même plus (per rapport à sa rédaction) :

alb12 @ 28-09-2018 à 22:42

Soit P une propriete definie sur N
Si:
1/ P(0) est vraie
2/ pour tout entier n, P(n) implique P(n+1) est vraie
alors pour tout entier n, P(n) est vraie.
on se fout des valeurs de vérité de P(n) et P(n + 1) mais on veut montrer que l'implication est vraie

et s'il existe un entier N tel que P(N) est vraie alors P(n) est vraie pour tout n >= N !!!

Posté par
Yzzre : Raisonnement par récurrence 29-09-18 à 08:08

Oui, mais on est évidemment tous d'accord là dessus (enfin, je crois) :
L'étape de l'hérédité consiste à prouver que P(n) vraie implique P(n+1) vraie aussi.
Cela n'enlève rien au pb : pour la montrer, cette hérédité, on suppose donc P(n) vraie pour un entier n.
Tout cela ne dit pas POURQUOI une rédaction commençant par "supposons qu'il existe un entier n tel que P(n) est vraie" n'est pas valable.

Et je reviens encore à la charge : On a trois phrases qui pour moi disent la même chose, SANS PARLER DE RAISONNEMENT PAR RECURRENCE, et si ce n'est pas le cas, est-il possible de savoir pourquoi ?
Je vous les remets ici, en changeant juste le type de variable, histoire de bien me faire comprendre :

Soit z un complexe quelconque et on suppose P(z) vraie.
Supposons P(z) vraie pour un complexe z quelconque.
Supposons qu'il existe un complexe z pour lequel P(z) est vraie.

Posté par
littleguyre : Raisonnement par récurrence 29-09-18 à 08:38

Bonjour Yzz,

D'accord avec toi.

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 09:15

je commence à douter...

Posté par
flightre : Raisonnement par récurrence 29-09-18 à 11:54

:D  100 kms de post pour une petite question ...

Posté par
alb12re : Raisonnement par récurrence 29-09-18 à 11:54

"et surtout pas de quantificateur" dit mousse42
je ne suis pas d'accord.

Imaginons une file d'attente infinie,
les numeros 1, 2, ..., 17 ont une casquette verte
le numero 18 a une casquette rouge
les numeros 19 et au delà ont une casquette verte

Soit P(n): le numero n a une casquette verte

1/ P(1) est vraie
2/ pour tout entier non nul, si P(n) est vraie alors P(n+1) est vraie
Cette assertion est fausse pour une seule valeur de n

Posté par
flightre : Raisonnement par récurrence 29-09-18 à 11:57

avec   2nn      ( proprieté qu'on suppose vraie à l'ordre n)
on veut montrer que celle ci reste vraie aussi à l'ordre n+1  
2.  2n2.n       soit    2n+12.n

mais comme n 1     que peux tu ajouter membre à membre  à
n 1 pour arriver  à 2n+1(n+1)

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 12:16

flight, quel est l'objet de ta question ?

alb12


Citation :
1/ P(1) est vraie
2/ pour tout entier non nul, si P(n) est vraie alors P(n+1) est vraie
Cette assertion est fausse pour une seule valeur de n


Non, tu pourras certainement montrer que \forall n\ge 19 ,\quad P(n)\implies P(n+1)
Sans connaître la valeur de vérité de P(k)

Et peut même étendre à n\ge 18, puisque P(18) est faux

Voir énoncé 2 p 39 du document pdf

Posté par
flightre : Raisonnement par récurrence 29-09-18 à 12:21

arriver au but pardi !

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 12:26

flight

avec l'hypothèse P(n): 2^n\ge n

2^{n+1}\ge n+1

donc 2^n\ge 1\implies 2^{n+1}\ge n+1

donc 2^n\ge 1\iff n\ln 2\ge 0\iff n\ge 0

\forall n\ge 0, P(n)\implies P(n+1)

Posté par
carpediemre : Raisonnement par récurrence 29-09-18 à 12:29

les assertions :

F => F
F => V
V => V

sont vraies

donc la propriété P(n)  :  2^n > n est vraie (héréditaire) pour tout entier n

et la propriété P(2) est vraie

donc la propriété P(n) est vraie pour tout entier n supérieur à 2

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 12:31

C'est mal rédigé (j'ai cliqué trop vite)

Soit P(n): 2^n\ge n
Hérédité :

Soit n\in \mathbb{N} et on suppose P(n) vraie

On va montrer que 2^{n+1}\ge n+1

Puisque 2^n\ge 1\implies 2^{n+1}\ge n+1 par hypothèse de récurrence (on cherche une condition suffisante)

Ainsi il suffit que 2^n\ge 1 pour que P(n+1) soit vraie

et puisque 2^n\ge 1\iff n\ln 2\ge 0\iff n\ge 0

Il s'ensuit que \forall n\ge 0, P(n)\implies P(n+1)

flight par contre je ne vois pas où tu veux en venir

Posté par
alb12re : Raisonnement par récurrence 29-09-18 à 12:48

Il s'ensuit que \forall n\ge 0, P(n)\implies P(n+1)
c'est ce que je me tue à dire !

Posté par
carpediemre : Raisonnement par récurrence 29-09-18 à 12:51

moi itou ...

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 12:55

je parlais de quantificateur dans la preuve

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 13:04

mousse42 @ 29-09-2018 à 12:16

flight, quel est l'objet de ta question ?

alb12


Citation :
1/ P(1) est vraie
2/ pour tout entier non nul, si P(n) est vraie alors P(n+1) est vraie
Cette assertion est fausse pour une seule valeur de n


Non, tu pourras certainement montrer que \forall n\ge 19 ,\quad P(n)\implies P(n+1)
Sans connaître la valeur de vérité de P(k)

Et peut même étendre à n\ge 18, puisque P(18) est faux

Voir énoncé 2 p 39 du document pdf


attention P(n) est héréditaire à partir de P(19) et pourtant :

on a bien \forall n\ge 18 ,\quad P(n)\implies P(n+1)



Donc \forall n (P(n)\implies P(n+1) n'est pas synonyme d'hérédité. l faut faire le distingo, et le langage mathématique ne permet pas de le faire

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 13:28

bon, je laisse ce sujet pour plus tard, je pars bosser... peut-être faudrait-il créer une discussion dans expresso ou dans espace prof sur le principe de récurrence et sa rédaction, puisque selon l'étude (pdf joint), des erreurs sont bien présentes dans les ouvrages scolaires.

Posté par
mousse42re : Raisonnement par récurrence 29-09-18 à 13:42

elevedeTeS désolé d'avoir pollué ta discussion, je viens seulement de m'en rendre compte.

J'espère que tu trouveras ton bonheur, sinon n'hésite pas à reposer ta question.

Bon courage

Posté par
malou Webmasterre : Raisonnement par récurrence 29-09-18 à 13:44

Citation :
des erreurs sont bien présentes dans les ouvrages scolaires.

tu découvres là ? ....
un manuel scolaire n'est en rien une référence...

Posté par
flightre : Raisonnement par récurrence 29-09-18 à 17:33

puisqu'on  a  2n+12n
comme  n1   alors  n+n n+1  soit  
2nn+1     alors  
2n+12nn+1   soit donc
2n+1n+1

Posté par
alb12re : Raisonnement par récurrence 30-09-18 à 15:48

une saine lecture , specialement la page 2.
l'implication doit etre vraie pour tout n car sinon
on ne pourrait pas affirmer que P(n) est vraie pour tous les entiers.
On omet souvent le "quel que soit n"
A minima on peut ecrire
"Soin n un entier quelconque. Supposons etc ..."
ou
"Soin n un entier quelconque. si P(n) est vraie alors etc ..."

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

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

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

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 !