Raisonnement par l'absurde

[Anonyme]

Salut, je rentre en prépa MPSI à la rentrée et donc je suis en train de lire en diagonale le programme de l'année. Je bute sur un paragraphe, que je n'arrive pas à comprendre, quelqu'un pourrait-il me l'expliquer, me donner un exemple ou autre svp ? :triste:

Voilà le paragraphe :

"Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On cherche ensuite un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction."

Voilà c'est le flou total... on cherche un k, mais comment ? Et puis vu qu'on connaît pas h0, comment montrer k < h0 ?

Merci d'avance :++:

[muse]

Mouais c'est pas le genre de raisonnement qu'on utilise tous les jours...Je parle du raisonnement par l'absurde pour montrer qu'une propriété est vrai sur N. Par contre le raisonnement par l'absurde est souvent utilisé, par exemple pour montrer que quelque chose est unique.

Bon je comprends que ce ne soit pas tres claire c'est pas evident. Le but est de montrer que P(n) est vrai pour tout n. On te dis qu'on considere un h0 tel que P(h0) soit faux. Bien sur ce h0 n'existe pas !!!!! sinon on te demande de demontrer qqch de faux .... Tu comprends ?
h0 est le plus petit nombre de N tel que P(h0) est faux. Donc normalement, puisque c'est le plus petit, tu peux pas en trouver un h1
Donc par exemple tu dis a un moment "Soit h le plus petit nombre tel que P(h0) soit faux." Ensuite avec un petit calcul tu arrive a montrer que si p(h0) est faux alors p(h0-1), par exemple, est faux aussi et que donc h0 n'est pas le plus petit d'ou la contradiction

Je ne sais pas si j'ai été claire ...

[leon1789]

"Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On cherche ensuite un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction."

(source http://www.zonegeeks.com/Documents/Cours/prepa/maths/chpt_11_ensemble_fini_denombrement.pdf)

Mouais c'est pas le genre de raisonnement qu'on utilise tous les jours...Je parle du raisonnement par l'absurde pour montrer qu'une propriété est vrai sur N.

En effet, ce genre de raisonnement par l'absurde prouvant que P(n) est vrai pour tout entier n, est exactement la contraposition d'un raisonnement bien connu : le raisonnement par récurrence sur P(n) !!

Autrement dit, tout ce que l'on peut démontrer par ce type de raisonnement par l'absurde (qu' aarnaud a visiblement du mal à comprendre) peut se prouver aussi par une récurrence (qu' aarnaud a certainement déjà compris)... et réciproquement.

Donc, ceux qui aiment faire dans l'absurde vont choisir ce type de raisonnement par l'absurde, ceux qui aiment les récurrences choisiront la récurrence. Mais quel que soit le choix de l'auteur de la preuve, les deux raisonnements utiliseront au final les mêmes arguments...

Les différences entre ces deux raisonnements se situent, d'une part, dans des rédactions différentes (malgré des arguments essentiellement identiques), et d'autre part, dans ce que l'on peut en retenir a posteriori (sans parler d'axiomatique).

[leon1789]

[quote="aarnaud"]
Voilà c'est le flou total... on cherche un k, mais comment ? Et puis vu qu'on connaît pas h0, comment montrer k P(h0 -1) faux" (ce qui aboutit à cette fameuse contradiction puisque h0 est le plus entier naturel tel que P(h0) soit faux) ,
alors que dans l'hérédité d'une récurrence, on montre "P(h0 -1) vrai => P(h0) vrai" (ce qui montre une propagation de la propriété sur N)

Quand on compare les implications "P(h0) faux => P(h0 -1) faux" et "P(h0 -1) vrai => P(h0) vrai", on voit clairement le principe de contraposition dont je parlais dans le message précédent.


Je pense qu'on devrait illustrer tout cela avec un petit exemple, non ?

[leon1789]

Par contre le raisonnement par l'absurde est souvent utilisé, par exemple pour montrer que quelque chose est unique.

:triste: Je pense que le raisonnement par l'absurde est utilisé de manière abusive, car souvent il est formé d'un raisonnement "direct" que l'on a surchargé malheureusement de contradiction (entrainant instantanément une perte d'informations...).

[leon1789]

Voilà le paragraphe :

"Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On cherche ensuite un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction."

:doh: :doh: D'ailleurs, ce paragraphe est incomplet :marteau: il manque le cas où h0 est nul...

Pour raisonner correctement, il faut montrer que h0 n'est pas nul (ce qui est évidemment en liaison avec l'initialisation du raisonnement par récurrence, dont je parlais au-dessus). Ainsi, on doit corriger ainsi le paragraphe :

Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On montre que h0 n'est pas nul. On peut alors chercher un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction. (le plus souvent, prendre k = h0 -1.)

Je crois qu'un petit exemple pour illustrer tout ça est obligatoire, non ?

[leon1789]

Voilà le paragraphe :

"Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On cherche ensuite un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction."

:doh: :doh: D'ailleurs, ce paragraphe me paraît "incomplet" :marteau: Dans l'hypothèse où h0 est nul, on ne pourra pas trouver un entier naturel k < h0 tel que... Il faut traiter le cas où h0 est nul à part.

Pour raisonner correctement, il faut montrer que h0 n'est pas nul (ce qui est évidemment en liaison avec l'initialisation du raisonnement par récurrence, dont je parlais au-dessus). On doit corriger ainsi le paragraphe :

Pour montrer par l'absurde qu'une propriété P(n) est vraie pour tout entier n appartenant à N, on suppose qu'il existe au moins un entier h tel que P(h) est faux ; on peut alors considérer le plus petit entier h0 tel que P(h0) est faux. On montre que h0 n'est pas nul. On peut alors chercher un k appartenant à N tel que k < h0 et P(k) est faux pour aboutir à une contradiction. (le plus souvent, prendre k = h0 -1.)

Je crois qu'un petit exemple pour illustrer tout ça est obligatoire, non ?

[Anonyme]

Merci j'ai déjà un peu mieux compris ! Si vous avez un exemple sous la main, pourquoi pas :id:

[muse]

Tu peux essayer de demontrer egalité. C'est un exercice tres connu, tu l'as peut etre deja fait.

[Ericovitchi]

si je peux me permettre, c'est qui vaut n(n+1)(2n+1)/6
ça tend vers quand n tend vers l'infini mais c'est tout ce que l'on peut dire

[Anonyme]

Ok merci voyons si j'y arrive :

Je suppose qu'il existe un k tel que

1 + 2² + ... + k² n'est pas égal à k(k+1)(2k+1)/6

h = k-1, donc k = h+1

1 + 2² + ... + h² + (h+1)² = 1 + 2² + ... + 2h² + 1 + 2h

il faut donc montrer que ça, c'est pas égal à h(h+1)(2h+1)/6, on sait que c'est pas égal à k(k+1)(2k+1)/6, donc en mettant k=h+1, c'est pas égal à :

(h+1)(h+2)(2h+3)/6. On enlève le h²+2h+1 qui était en trop mais d'abord on développe :

(2h^3 + 6h² + 4h +3h² + 9h + 6)/6

2h^3 + 9h² + 13h + 6 /6, on enlève h²+2h+1 ([6h²+12h+6]/6) :

2h^3 + 3h² + h / 6

= h(h+1)(2h+1)/6

donc 1 + 2² + ... + h² n'est pas égal à h(h+1)(2h+1)/6


c'est bon ? :id:

[leon1789]

Oui, pour l'instant, c'est bien ça :zen:

on suppose qu'il existe un k tel que
1 + 2² + ... + k² k(k+1)(2k+1)/6

On pose h = k-1, donc k = h+1, d'où
1 + 2² + ... + h² + (h+1)² (h+1)(h+2)(2h+3)/6.

On soustrait (h+1)² de chaque coté et on arrive à
1 + 2² + ... + h² h(h+1)(2h+1)/6


Attention, tu n'as pas justifié que h est un entier naturel. Cela reste à faire.
De plus, il faut terminer le raisonnement par l'absurde.

[Anonyme]

Je ne comprend pas : si k est un entier naturel, forcément h aussi puisque h = k-1 non ?

Pour finir le raisonnement par l'absurde :

donc k n'est pas le plus petit
donc c'est absurde

C'est tout non ? :zen:

[leon1789]

Je ne comprend pas : si k est un entier naturel, forcément h aussi puisque h = k-1 non ?

non, pas toujours... Il existe un (et un seul) entier naturel k tel que k-1 ne soit pas un entier naturel : tu ne vois pas lequel ?
(indication : rappelle-toi, ce raisonnement par l'absurde est un raisonnement par récurrence déguisé... :id:)

Pour finir le raisonnement par l'absurde :

donc k n'est pas le plus petit
donc c'est absurde

C'est tout non ? :zen:

Oui, une fois que tu auras montré que h est un entier naturel :++:

[Anonyme]

Ah, il faut pas que k=0 c'est ça ?

On montre que 0²=0(1)(1)/6

Donc k =/= 0 car avec 0, la proposition est vraie !

[leon1789]

Ah, il faut pas que k=0 c'est ça ?

On montre que 0²=0(1)(1)/6

Donc k =/= 0 car avec 0, la proposition est vraie !

Exactement ! :we:

En résumé :
on suppose qu'il existe un k minimal parmi les entiers naturels tels que
1 + 2² + ... + k² k(k+1)(2k+1)/6

Or la proposition désirée est vraie pour l'entier 0, donc .

On pose h = k-1 , donc k = h+1, d'où
1 + 2² + ... + h² + (h+1)² (h+1)(h+2)(2h+3)/6.

On soustrait (h+1)² de chaque coté et on arrive à
1 + 2² + ... + h² h(h+1)(2h+1)/6

Or ceci contredit le fait que k est le plus entier naturel réalisant l'inégalité... contradiction...


Vois-tu maintenant clairement le lien entre ce raisonnement par l'absurde et une simple récurrence (initialisation + hérédité) ? Ici, on a utilisé en fait les mêmes arguments dans ce raisonnement par l'absurde qu'on l'aurait fait dans une récurrence. Non ?

[Anonyme]

Merci ça y'est j'ai compris :++: merci