Inscription / Connexion Nouveau Sujet
Démonstration théorème de récurrence
Bonsoir!
Je n'arrive pas à comprendre la démonstration du théorème de récurrence. Dans le cours, nous avons l'énoncé du théorème :
Soit P(n) l'affirmation qui porte sur un entier naturel n. Si l'affirmation P(0) est vraie, et si pour tout entier n, l'affirmation P(nà implique l'affirmation P(n+1), alors on peut affirmer que l'affirmation P(n) est vraie pour tout entier n.
Jusque là, ça va. Mais la démonstration, j'arrive pas à suivre :
Soit K l'ensemble de tous les entiers n tels que P(n) est faux. On doit prouver que K est vide pour établir le théorème. Raisonnons par l'absurde et supposons K non vide. K contient donc au moins un entier. Le plus intéressant élément de K est le plus petit que nous noterons s. (jusque là ça va) Comme P(0) est vraie, 0 n'est pas dans K donc s>0 donc s
1, (là j'imagine qu'ils partent d'une hypothèse de départ avec une conjecture vraie pour n=0), notons t = s - 1 0 (et là c'est le drame, je comprends plus rien...) L'entier t étant plus petit que s ne peut être dans K puisque s est ce qui se fait de plus petit dans K. Il en résulte que P(t) est vraie, donc P(t+1) c'est à dire P(s) est également vraie. Ceci contredit le fait que s est dans K, donc que P(s) est faux. Cette contradiction prouve que K est nécessairement vide.
Quelqu'un pourrait-il m'éclairer à ce sujet? Particulièrement sur ce qu'est t, et pourquoi si P(t) vraie alors P(t+1) l'est aussi...
Merci d'avance!
Bonjour
t = s-1. s est le plus petit entier tel que P(s) soit faux. Donc puisque t est plus petit que t, P(t) est vrai (sinon le plus petit entier tel que P(s) soit faux serait t, pas s). Et si P(t) est vraie, alors P(t+1) l'est aussi par hypothèse de récurrence.
Bonjour,
Avant la démonstration, est-ce que tu comprends le théorème, et est-ce que tu en as vu des applications ? 
pourquoi si P(t) vraie alors P(t+1) l'est aussi...
Par hypothèse.
Les hypothèses du théorème sont :
- P(0) est vraie
- si P est vraie à un rang alors elle l'est aussi au rang suivant (ce qui se note : P(n) implique P(n+1))
La conclusion du théorème : La propriété P est vraie pour tous les entiers.
J'ai reformulé la démonstration, mais je ne sais pas vraiment si ça va t'aider...
On suppose au début de la démonstration que P(n) est vrai, alors P(n+1) l'est aussi => P(t) => P(t+1). Pour la démonstration en elle même, on a :
-> une propriété P telle que P(n) => P(n+1) et P(0).
-> un ensemble K qui ne possède que les éléments k tels que P(k) est faux.
On veut prouver :
-> que K est vide.
On suppose :
-> que K possède au moins un élément (raisonnement par l'absurde), et que le plus petit élément est s.
Or, pour tout élément k de K, !P(k) (= non P(k)) => !P(s) puisque s est dans K. Or, P(0), donc s != 0. => s > 0 puisqu'on travaille dans N.
On pose t = s-1. Or s > 0 => s >= 1 => s-1 >= 0 => t >= 0. s étant le plus petit élément de K et t étant inférieur à s, t n'appartient pas à K. Or, K contient tous les éléments k tels que P(k) est faux. Donc P(t) est vrai puisqu'il n'est pas dans k. Or P(n) => P(n+1) donc P(t) => P(t+1). Or, t = s-1 => t+1 = s. Donc P(s) est vrai. On a ici une contradiction car s appartient à K, ce qui est équivalent à non P(s).
Au final, on a forcément un ensemble K vide, donc tous les éléments x ne lui appartenant sont tels que P(x) est vrai.
Merci beaucoup pour vos réponses si rapides! En ce qui concerne le théorème, c'est bon. J'ai déjà fait quelques exemples d'applications en cours, mais comme on a tout bouclé en moins de 2h, ca a été un peu vite ^^ Enfin la, je crois avoir compris, donc comme s est le plus petit élément qui est dans K et que t < s, ca veut dire que t n'est pas dans K et donc que P(t) est vraie. Comme P(0) est vraie, alors P(t+1) est aussi vraie. Or t+1=s, d'où P(s) vraie, ce qui est contradictoire, d'où K vide et le théorème vérifié. C'est juste? En fait, la démonstration est pas réellement une démonstration du théorème, mais plutot une sorte d'application, vu qu'on se sert du théorème dans la démonstration non?
On ne se sert nulle part du théorème.
Si un théorème a une hypothèse H et une conclusion C, pour le prouver
- tu supposes que H est vrai
--> et tu montres que dans ce cas C est vrai
On n'utilise, dans la démonstration, que l'hypothèse H (ou les hypothèses, s'il y en a plusieurs comme ici).
Si j'ai bien compris, on cherche juste à prouver qu'il n'a aucun entier n tels que P(n) faux, si P(0) vraie et P(n) implique P(n+1) c'est ça?
Oui, voilà. Pour démontrer ça, on suppose qu'il en existe (l'ensemble K), et on prouve que ça contredit les données de départ.
Annuler
connectez vous