Inscription / Connexion Nouveau Sujet
Raisonnement par récurrence
Bonjour, je m'entraîne pour un contrôle et j'aurai aimé savoir si mon raisonnement était le bon.
Merci d'avance.
Exercice:
Montrer que 2^n>=n pour tout n>=1
Réponse:
Démontrer que pour tout entier naturel n, on a: 2n>=n avec n>=1
Initialisation:
Démontrons que la propriété est vraie pour n=0
2^n>=n
2^0=1>=0
Hérédité:
hypothèse de récurrence: supposons qu'il existe un entier k tel que la propriété soit vraie:
2^k>=k
à démontrer: la propriété est vraie au rang k+1:
2^k+1>=(k+1)
2^k+1=2^k(k+1)
=k(k+1)
Conclusion: la propriété est vraie pour n=0 et héréditaire à partie de ce rang.
salut
à démontrer: la propriété est vraie au rang k+1:
2^k+1>=(k+1)
2^k+1=2^k(k+1)
=k(k+1)
et comment tu passes de la première à la deuxième ligne ...
du grand n'importe quoi !!!
Salut,
Exercice:
Montrer que 2^n>=n pour tout n>=1
Initialisation:
Démontrons que la propriété est vraie pour n=0
Un des deux à rectifier...
Salut
Et la rédaction n'est pas bonne
Hérédité:
hypothèse de récurrence: supposons qu'il existe un entier k tel que la propriété soit vraie:
Si on note
Pour l'hérédité, on dit ceci.
On va montrer que pour tout
Ensuite on choisit un
Et on montre que
J'ai pourtant essayé de suivre les étapes de la vidéo et c'est bien le seul moyen qui me permet de comprendre plus ou moins le raisonnement par récurrence
--> mousse42 :
En quoi cette rédaction "n'est pas bonne" ?
Hérédité:
hypothèse de récurrence: supposons qu'il existe un entier k tel que la propriété soit vraie:
2^k>=k
à démontrer: la propriété est vraie au rang k+1:
2^(k+1)>=(k+1)
on en dit pas ce qu'on fait, on le fait et on conclut ...
PS : mais c'est un détail de forme ... malheureusement nécessaire de nos jours ...
Dire que qu'il existe un k tel que P(k) soit vraie et montrer P(k+1), ça veut dire qu'il existe un tel que
, et après on est bien avancé car on n'a pas montrer que
ni même
--> mousse42 :
(Sans vouloir parasiter le sujet de elevedeTeS) :
Je prouve que P(0) est vraie.
Puis :
"Supposons qu'il existe un entier k tel que P(k) soit vraie" , et je démontre qu'alors alors P(k+1) est vraie aussi.
D'après toi, cela ne prouve pas que P(1) est vraie ?
ouais c'est un détail de forme ... je rejoins Yzz
la récurrence c'est montrer que la proposition P(n) => P(n + 1) est vraie quelle que soit la valeur de vérité de P(n)
évidemment puisque F => F est vraie ... mais n'a aucun intérêt (EX : le cas qui nous intéresse est bien sur V => V
on suppose donc que P est vraie et c'est notre hypothèse de récurrence
et on se fout donc de savoir s'il existe ou pas un entier n tel que P(n) est vraie
évidemment une fois l'hérédité établie il nous importe bien sur de savoir si elle est vraie pour un entier m et alors on pourra initialiser l'hérédité pour affirmer que P(n) est vraie pour tous les entiers supérieurs à m
supposer P(n) vraie n'est pas supposer qu'il existe un k tel que P(k) est vraie
c'est simplement affecter la valeur de vérité vrai à une affirmation sans savoir si elle est effectivement vraie ou fausse comme le montre d'ailleurs mon exemple ...
je ne dis pas qu'il existe un n tel que 10^n + 1 est multiple de 9 est vraie
je dis simplement supposons que 10^n + 1 est multiple de 9
...
carpediem, tu nois le poisson, ton argumentaire n'est pas convaincant, en tout cas tu ne reponds pas à la question posée.
Evidemment on ne s'intéresse pas à savoir si P(n) est vraie ou non.
Simplement dire qu'on suppose qu'il existe un tel que
est vraie est formellement faux.
On doit montrer que
je suis sûr que si un de tes étudiants commencent par dire supposons qu'il existe un tel que
soit vraie pour démontrer l'implication ci-dessus tu vas lui souffler dans les bronches
il y a des croisés le message de 22:48 est destiné à Yzz
Le dernier message est destiné à carpediem suite au message de 22:42
Je saisis ce que tu veux dire.
Mais je continue à penser que formellement, la rédaction proposée par elevedeTeS reste correcte.
Comme pour le TVI, il existe à peu près une rédaction par prof ; l'inconvénient étant que certains d'entre eux pensent détenir la vérité ultime et dénoncent tous les autres comme hérétiques.
Ce qui n'est manifestement pas ton cas...
Du moins à ce que j'ai pu lire :
Carpediem, tu es bien d'accord, non?
Non, je ne pense pas,
J'en suis sûr à 99.999%
"Ma" propre rédaction de l'hérédité donne :
" Supposons P(k) vraie pour un entier k : (...) "
Ton avis ?
En toute cordialité,
Yzz
Salut Yzz
Pour le TVI, il y a plusieurs rédactions en effet, si l'une n'est pas correct, on peut le démontrer.
On m'a appris que pour montrer , on prend un
quelconque et on montre
à partir de
(qu'on suppose vraie) . Ce qui me paraît logique, puisque si c'est vrai pour un
quelconque on conclut que c'est vrai pour tout
Lorsque l'on veut montrer que , Dire ceci "On suppose qu'il existe un
tel que
est vraie" n'est pas correct puisque formellement ça s'écrit
Ainsi on vérifie l'implication que pour un certain , et pas pour tous les
Je vais essayer de trouver le document qui explique comment rédiger une preuve, et qui précise les erreurs les plus courantes.
Pour info, je ne dénonce personne comme hérétique, c'est le plaisir de faire des maths, c'est tout et de discuter sur des points, qui peuvent induire l'éléve en erreur.
"Ma" propre rédaction de l'hérédité donne :
" Supposons P(k) vraie pour un entier k : (...) "
Ton avis ?
Carpediem
Je pense avoir bien compris le principe de l'héredité, montrer que
Sans rien savoir de la valeur de vérité de
Donc l'hérédité n'est plus un problème pour moi comme tu le sous-entends
je suis désolé d'être trop pointilleux, c'est certainement dû au fait que je passe trop de temps sur ce forum, et à force de prendre des coups de massue, la rigueur mathématique est devenue ma règle, faudrait pas me le reprocher maintenant
bof ...
comme je l'ai dit l'hérédité consiste à montrer que :
si P(n) est vraie alors P(n + 1) est vraie est une proposition vraie
et évidemment puisque P(n) dépend par définition de l'entier n c'est sous-entendre : supposons qu'il existe un entier k tel que P(k) est vraie ...
si P(n) est la proposition : 10^n + 1 est multiple de 9
ben trouve moi un entier k tel que P(k) est vraie !!!
donc on ne travaille que sur les valeurs de vérité des propositions P(n), P(n + 1) et P(n) => P(n + 1)
et l'hérédité consiste à prouver que la troisième est vraie quand on suppose que la première est vraie (et qui conduit à conclure que P(n + 1) est vraie)
et la propriété ne sera vraie que s'il existe réellement un entier n_0 tel que P(n_0) est vraie
toujours avec la même proposition et puisque la proposition F => F est vraie alors la troisième proposition est vraie toujours (puisque P(n) est toujours fausse)
et quand je suppose P(n) vraie je prouve que P(n + 1) l'est aussi donc que la troisième proposition l'est aussi
mais ne pouvant initialiser je ne prouve simplement que F => F est vraie
et prouver une tautologie n'a guère d'intérêt ...
si P(n) est la proposition : 10^n + 1 est multiple de 9
ben trouve moi un entier k tel que P(k) est vraie !!!
Je vois que tu ne lis pas mes messages.
J'ai jamais dit qu'on cherche à montrer que
En supposant qu'il existe
Supposons qu'il existe, on devrait pourvoir le nommer, on l'appelle
On montre
Et là on est bien avancé, on ne sait même pas si
ben justement on ne suppose pas qu'il en existe un (d'entier) on suppose que P(n) est vraie !!!
et je prouve que pour tout n : P(n) => P(n + 1) est vraie bien que je ne puisse exhiber aucun entier n tel que P(n) soit vraie ...
Salut
Et la rédaction n'est pas bonne
Hérédité:
hypothèse de récurrence: supposons qu'il existe un entier k tel que la propriété soit vraie:
Si on note
Pour l'hérédité, on dit ceci.
On va montrer que pour tout
Ensuite on choisit un
Et on montre que
Donc j'ai raison
, merci carpediem
Pour info, je ne dénonce personne comme hérétique, c'est le plaisir de faire des maths, c'est tout et de discuter sur des points, qui peuvent induire l'éléve en erreur.
Moi-même je ne cherche nullement à "prouver que j'ai raison", après tout peut-être ai-je tort, et quand je l'aurai compris (si cela se produit) , j'en ressortirai moins ignorant.
J'ai toujours en tête une phrase émise par un dessinateur de BD un peu "torturé" , au détour d'une interview : "Si vous avez des certitudes, c'est que vous êtes mal informé".
Je reprends donc, dans un souci de clarification :
Soit n quelconque et on suppose P(n) vraie.
Supposons P(n) vraie pour un entier n quelconque.
Supposons qu'il existe un entier n pour lequel P(n) est vraie.
SANS parler du principe du raisonnement par récurrence (je n'évoque ici nullement l'implication "alors P(n+1) est vraie aussi" que l'on doit prouver) , je ne vois toujours pas ce qui différencie clairement les trois propositions ci-dessus.
... J'ajoute que justement, la première et la deuxième formulation : "Soit n quelconque et on suppose P(n) vraie." sont celles qui pourront le plus induire en erreur un élève "lambda", qui traduira cela (consciemment ou non) par : "supposons P(n) vraie pour n'importe quel entier n"... et le fera passer complètement à côté du sujet.
et je suis d'accord avec Yzz : l'important c'est de supposer la propriété vraie ... et évidemment puisqu'elle dépend d'un entier ... ben ça devient explicitement : supposons la propriété vraie pour un entier n
j'éviterai même le mot quelconque qui peut induire le raccourci : quelconque = n'importe lequel = tous !!!
que l'on trouve évidemment sur certaines copies ...
Ecoute Yzz, je ne juge personne, je fais des maths et rien de plus :
Soit n quelconque et on suppose P(n) vraie.
Supposons P(n) vraie pour un entier n quelconque.
Supposons qu'il existe un entier n pour lequel P(n) est vraie.
1 et 2 sont corrects (c'est la même chose), le 3 ne l'est pas, voir le fichier pdf plus haut.
On a le droit d'avoir quelques certitudes, je ne doute pas du théorème de Pythagore, par exemple. Quand j'ai dit que j'étais sûr à 99.99%, j'exprime simplement mon ressenti, et je ne juge personne.
Il m'arrive d'avoir des incertitudes aussi, et là je travaille, j'essaie de comprendre pour transformer ces incertitudes en certitudes.
Et pour finir, je ne suis pas encore professeur, je n'ai donc aucune expérience, si tu es contraint de faire des ajustements pour que les éléves comprennent, libre à toi, néanmoins ce n'est pas de ça qu'il est question dans cette discussion.
l'important n'est pas qu'il y ait un entier n ou pas tel que P(n) soit vraie !!!
l'important c'est de supposer P(n) vraie !!!!
on se fout de savoir si n existe ou pas !!! c'est une variable muette !!!
dans toute ma carrière d'élève et d'étudiant je n'ai jamais initié avant de récurer !!! (1)
ce qui compte dans ce raisonnement et dans son apprentissage et dans l'activité intellectuelle mathématique c'est de faire une démonstration, un raisonnement : une suite logique d'opérations intellectuelles valides !!! celle de l'hérédité dans le cas d'un raisonnement par récurrence évidemment
(1) ... sauf évidemment les (quelques rares) cas pathologiques ou triviaux où initier avant de récurer avait évidemment un intérêt pour récurer ....
de plus l'initialisation est une trivialité consistant à 99% à remplacer une variable par une valeur dans une expression où une (in)égalité pour la vérifier
il suffit de regarder les posts concernant les fora de math sur la récurrence pour comprendre l'état catastrophique de délabrement du raisonnement ... et de la capacité des élèves à en mener un ...
mousse42 :
Encore une fois, nous sommes d'accord : le but de cet échange est purement didactique (ou sémantique, allez savoir) , et je poursuis dans cet esprit de confrontation des arguments sans aucune idée de vouloir imposer un point de vue : c'est ce que je crois pouvoir constater de ta part aussi, et ce qui rend ce dialogue passionnant.
Peut-être vas tu trouver que je pousse trop loin mes interrogations (auquel cas, nous cesserons cet échange qui me semble pourtant très intéressant intellectuellement).
Mais je reprends ma précédente question :
SANS parler du principe du raisonnement par récurrence (je n'évoque ici nullement l'implication "alors P(n+1) est vraie aussi" que l'on doit prouver) , je ne vois toujours pas ce qui différencie clairement les trois propositions ci-dessous :
Soit n quelconque et on suppose P(n) vraie.
Supposons P(n) vraie pour un entier n quelconque.
Supposons qu'il existe un entier n pour lequel P(n) est vraie.
Tu m'évoques le document joint, qui semble-t-il "contextualise" ces propositions ; et du reste la troisième en question (la mienne) n'est pas formellement celle citée dans ce document.
Mais on peut les considérer comme trois propositions totalement indépendantes du "raisonnement par récurrence" : elles concernent toutes les trois une propriété portant sur les nombres entiers naturels. (On pourrait d'ailleurs écrire la même chose en remplaçant n entier par x réel, z complexe, M matrice, f fonction etc...)
Je te demande donc, si tu le veux bien, de m'éclairer sur la (ou les) différence(s) formelle(s) entre les deux premières et la troisième.
Personnellement, je n'en vois pas.
PS :
Je suis bien sûr d'accord avec carpediem. C'est pas toujours le cas, donc j'en profite pour le dire ! 
c'est ce que je crois pouvoir constater de ta part aussi, et ce qui rend ce dialogue passionnant.
C'est exactement ce que je recherche, par contre laisse moi du temps pour développer mon argumentation
salut,
pour avoir une idee de la bonne formulation on peut revenir à la demonstration du principe de récurrence.
Annuler
connectez vous