Qu'est-ce que la méthode de la preuve par épuisement ?
La preuve par épuisement est une méthode de preuve directe. Elle peut prendre beaucoup de temps, car il peut y avoir beaucoup de cas à vérifier. Il est possible de diviser les cas, par exemple les nombres pairs et impairs.
La preuve par épuisement est différente des autres méthodes de preuve directe, car nous n'avons pas besoin de tirer des arguments logiques. Il suffit de montrer qu'"aucun des cas ne réfute la conjecture ; la conjecture est donc vraie". La preuve par épuisement n'est utilisée que lorsqu'il y a un nombre fini de cas.
Comment prouver l'épuisement ?
Nous pouvons généraliser la méthode de la preuve par épuisement en utilisant deux étapes.
Étape 1 : Établir les cas qui s'appliquent à l'énoncé.
Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.
Chaque cas de l'affirmation doit être prouvé séparément, un par un. Nous devons épuiser tous les cas pour vérifier l'affirmation.
Si l'un des cas identifiés peut être réfuté, l'ensemble de la conjecture peut être considéré comme réfuté. Tu peux consulter la section Démonstration par contre-exemple pour approfondir ce concept.
Prenons un exemple pour comprendre comment appliquer les étapes ci-dessus.
Montre que \(n^2-1\) est un multiple de 3 si n n'est pas un multiple de 3.
Solution :
Étape 1 : Si n n'est pas un multiple de 3, il est soit un, soit deux de plus qu'un multiple de 3. Nous pouvons donc écrire \(n = 3k + 1\) ou \(n = 3k + 2\), k étant un entier quelconque.
Étape 2 : Prouve maintenant que l'énoncé est vrai pour chaque cas.
Cas 1 : Montre que si \(n = 3k + 1\), alors \(n^2-1\) est un multiple de 3.
\N-(\N- Début{align} n^2-1 &= (3k + 1)^2 -1 \N- &= (3k)^2 + 6k +1-1 \N- &=9k^2 +6k \N- &=3(3k^2 + 2k) \N- Fin{align}\N)
Comme \N(3 (3k^2 + 2k)\Nest 3 fois \N((3k² + 2k)\N), nous pouvons conclure que \N(3 (3k^2 + 2k)\Nest un multiple de 3.
Ainsi, \(n^2 -1\) est un multiple de 3 pour \(n = 3k + 1\).
Vérifions maintenant le deuxième cas.
Cas 2 : Pour vérifier si \(n = 3k + 2\), alors \(n^2 -1\) est un multiple de 3.
\(\N- Début{align} n^2-1 &= (3k+2)^2 -1 \N- (3k)^2 + 2(3k)(2) + 2^2-1 \N- 9k^2 +12k + 3 \N- 3(3k^2 + 4k + 1) \N- Fin{align}\N)
L'expression résultante \(3 (3k^2 + 4k + 1)\) est également un multiple de 3 pour toute valeur de k. Ainsi, \(n^2 -1\) est un multiple de 3 pour \(n = 3k + 2\).
Comme les deux cas satisfont à l'énoncé, nous avons prouvé que l'énoncé donné est correct.
Quand utiliser la preuve par épuisement
La preuve par épuisement n'est possible que lorsque nous pouvons réduire la conjecture à un nombre fini de cas. Par exemple, nous avons réduit la conjecture à deux cas possibles dans l'exemple ci-dessus. Supposons que nous essayions plutôt de résoudre la conjecture par preuve par épuisement pour toutes les valeurs possibles de n. Ce serait un processus sans fin puisque le domaine de n n'est pas borné, c'est-à-dire que n peut prendre un nombre infini de valeurs.
Si nous pouvons réduire la conjecture donnée à un petit nombre de cas possibles, dont chacun peut être prouvé (ou réfuté), alors il peut être bon d'utiliser la preuve par épuisement. Pour un très grand nombre de cas, la preuve par épuisement n'est généralement pas une approche très efficace.
Exemples de preuves par épuisement
Exemple 1 : Montre que \(p = n^2 + 2\) n'est pas un multiple de 4, où n est un entier, \(2 \leq n \leq 7\).
Solution :
Étape 1 : divise l'énoncé en un nombre fini de cas.
Il est donné que \(2 \leq n \leq 7\) et pour chaque valeur de n, nous devons vérifier si \(p = n^2 +2\) est un multiple de 4 ou non.
Nous aurons six cas, comme indiqué.
Cas 1 : n = 2
Cas 2 : n = 3
Cas 3 : n = 4
Cas 4 : n = 5
Cas 5 : n = 6
Cas 6 : n = 7
Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.
Prouvons chaque cas un par un.
Cas 1 : n = 2
Substitue n = 2 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (2)^2 + 2 = 6\)
Comme 6 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Deuxième cas : n = 3
Substitue n = 3 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (3)^2 + 2 =11\)
Comme 11 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Cas 3 : n = 4
Substitue n = 4 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (4)^2 + 2 = 18\)
Comme 18 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Cas 4 : n = 5
Substitue n = 5 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (5)^2 + 2 = 27\)
Comme 27 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Cas 5 : n = 6
Substitue n = 6 dans \(p = n^2+2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (6)^2 + 2 = 38\)
Comme 38 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Cas 6 : n = 7
Substitue n = 7 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.
\(p = (7)^2 + 2 = 51\)
Comme 51 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.
Comme tous les cas satisfont à l'énoncé. L'affirmation \N(p = n + 2\N) n'est pas un multiple de 4 lorsque n est un entier et \N (2 \leq n \leq 7\N) est correcte.
Exemple 2 : Si p est un nombre premier tel que \N(3 <p <25\N), alors prouve par épuisement que \N((p - 1) (p + 1)\Nest un multiple de 12.
Solution :
Étape 1 : divise l'énoncé en un nombre fini de cas.
Il est donné que p est un nombre premier tel que \(3 <p <25\), et pour chaque p, nous devons vérifier si \((p - 1) (p + 1)\) est un multiple de 12 ou non.
Les nombres premiers compris entre 3 et 25 sont 5, 7, 11, 13, 17, 19, 23.
Nous aurons sept cas, comme indiqué.
Cas 1 : p = 5
Cas 2 : p = 7
Cas 3 : p = 11
Cas 4 : p = 13
Cas 5 : p = 17
Cas 6 : p = 19
Cas 7 : p = 23
Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.
Prouvons chaque cas un par un.
Cas 1 : Vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 5.
\N- (\N- (p - 1) (p + 1) &= (5-1) (5 + 1) \N- &= (4) (6) \N- &= 24 \N- &= 2(12) \Nend{align}\N)
\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 5.
Cas 2 : Pour vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 7.
\N- (\N- (p - 1) (p + 1) &= (7-1) (7 + 1) \N- &= (6) (8) \N- &= 48 \N- &= 4 (12) \N- (p - 1) (p + 1) &= (7-1) (7 + 1) \N- &= (6) (8) \N- &= 48 \N- &= 4 (12) \N-)
\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 7.
Cas 3 : Pour vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 11.
\N- (p-1) (p + 1) &= (11-1) (11 + 1) \N- (10)(12) \N- (120) \N- (10 (12) \Nend{align}\N)
\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 11.
Cas 4 : Pour vérifier si (p - 1) (p + 1) est un multiple de 12 lorsque p = 13.
\N- (\N- (p - 1) (p + 1) &= (13-1) (13 + 1) \N- &= (12) (14) \N- &= 168 \N- &= 14 (12) \N- (p - 1) (p + 1) &= (13-1) (13 + 1) \N- &= (12) \N- (\N-)
\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 13.
Cas 5 : Pour vérifier si (p - 1) (p + 1) est un multiple de 12 lorsque p = 17.
\(\N- (p - 1) (p + 1) &= (17-1) (17 + 1) \N- &= (16) (18) \N- &= 288 \N- &= 24 (12) \N- (p - 1) (p + 1) &= (17-1) (17 + 1) \N- &= (16) (18) \N- &= 288 \N- &= 24 (12) \N- (p + 1))
\N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 17.
Cas 6 : Vérifier si \N((p - 1) (p + 1)\Nest un multiple de 12 lorsque p = 19.
\N- ((p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N&= 360 \N&= 30 (12) \N- (p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N-&= 360 \N-&= 30 (12) \N- (p + 1) \)
\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 19.
Cas 7 : Vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 23.
\N- ((p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N&= 360 \N&= 30 (12) \Nend{align} \)
\N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 23.
Ainsi, tous les cas satisfont l'énoncé. Par conséquent, l'affirmation, si p est un nombre premier tel que \(3 <p <25\), alors \((p - 1) (p + 1)\) est un multiple de 12, est correcte.
Exemple 3 : Si n est un entier positif, alors \(n^7-n\) est divisible par 7.
Solution :
Étape 1 : divise l'énoncé en un nombre fini de cas.
Il est donné que n est un entier, et pour chaque n, nous devons vérifier si \(n^7-n\) est divisible par 7 ou non.
Nous aurons sept cas, comme indiqué.
Cas 1 : n multiple de 7. Donc, \(n = 7q\), où q est un entier.
Cas 2 : n un de plus que le multiple de 7. Donc, \(n = 7q + 1\), où q est un nombre entier.
Cas 3 : n deux de plus que le multiple de 7. Donc, \(n = 7q + 2\), où q est un nombre entier.
Cas 4 : n trois plus que le multiple de 7. Donc, \(n = 7q + 3\), où q est un nombre entier.
Cas 5 : n quatre plus que le multiple de 7. Donc, \(n = 7q + 4\), où q est un nombre entier.
Cas 6 : n cinq plus que le multiple de 7. Donc, \(n = 7q + 5\), où q est un nombre entier.
Cas 7 : n six plus que le multiple de 7. Donc, \(n = 7q + 6\), où q est un nombre entier.
Étape 2 : prouve que l'énoncé est vrai pour chaque cas.
Factorisons d'abord l'expression \(n^7 -n\) et prouvons chaque cas un par un.
\N(n^7-n = n(n^6-1) = n((n^3)^2-1) = n(n^3+1)(n^3-1)\N)Puisque \N(x^2 -y^(x+y)(x-y)\N) :
\(n(n+1)(n^2-n+1)(n-1)(n^2+n+1)\)
Puisque \N(x^3 + y^3 = (x+y)(x^2-xy+y^2)\N et \N(x^3-y^3 = (x-y)(x^2+xy+y^2)\N).
Donc, \N(n^7-n = n(n-1)(n+1)(n^2-n+1)(n^2+n+1)\N)
Vérifions maintenant chaque cas un par un.
Cas 1 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q\), où q est un entier.
\(n^7-n\) a un facteur \(n = 7q\).
L'expression est donc divisible par 7.
Cas 2 : Pour vérifier que \(n^7-n\)est divisible par 7 pour, \(n = 7q + 1\), où q est un entier.
\N(n^7-n\N) a un facteur \N(n-1 = 7q + 1-1 = 7q\N).
L'expression est donc divisible par 7.
Cas 3 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q + 2\), où q est un entier.
\N(n^7-n\N) a un facteur
\(\N- début{align} n^2+n+1 &= (7q+2)^2 + 7q +2 +1 \N- 49q^2 +28q + 4+ 7q+2+1 \N- 49q^2 +35 q+ 7 \N- 7(7q^2 + 5q +1) \N- fin{align}\N)
L'expression est donc divisible par 7.
Cas 4 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q + 3\), où q est un entier.
\N(n^7-n\N) a un facteur
\N-(\N-{align} n^2-n + 1 &= (7q+3)^2 -(7q+3) +1 \N-{align} &= 49q^2 + 42q + 9-7q-3 + 1 \N-{align} &= 49q^2 + 35q + 7 \N-{align} &= 7 (7q^2 + 5q + 1) \N-{align}\N-{align})
L'expression est donc divisible par 7.
Cas 5 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q + 4\), où q est un entier.
\N(n^7-n\N) a un facteur
\N- (\N- Début{align} n^2 + n + 1 &= (7q+5)^2 - (7q+5)+1 \N- 49q^2 + 56q +16 +7q+4 +1 \N- 49q^2 + 63q+21 \N- 7(7q^2 +9q+3) \N- Fin{align} \N-)
L'expression est donc divisible par 7.
Cas 6 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q + 5\) où q est un entier.
\N(n^7-n\N) a un facteur
\N-(\N-{align} n^2-n+1 &= (7q +5)^2 -(7q+5) +1 \N-{align} &= 49q^2 + 70q+25 -7q-5 +1 \N-{align} &= 49q² + 63q + 21 \N-{align} &= 7(7q^2 + 9q+3) \N-{align} \N-{align})
L'expression est donc divisible par 7.
Cas 7 : Vérifier que \(n^7-n\) est divisible par 7 pour \(n = 7q + 6\), où q est un entier.
\N(n^7-n\N) a un facteur \N(n + 1 = 7q + 6 + 1 = 7q + 7 = 7 (q + 1)\N).
L'expression est donc divisible par 7.
Ainsi, tous les cas satisfont l'énoncé. Par conséquent, si n est un entier positif, alors \(n^7-n\) est divisible par 7.
La preuve par épuisement - Principaux points à retenir
La preuve par épuisement est utilisée lorsqu'il y a un nombre fini de cas.
Nous devons d'abord trouver les cas, puis essayer chacun d'entre eux pour montrer qu'il est vrai.
La preuve est terminée si toutes les valeurs sont vraies.
Apprends avec 8 fiches de Preuve par épuisement dans l'application gratuite StudySmarter
Nous avons 14,000 fiches sur les paysages dynamiques.
Tu as déjà un compte ? Connecte-toi
Questions fréquemment posées en Preuve par épuisement
À propos de StudySmarter
StudySmarter est une entreprise de technologie éducative mondialement reconnue, offrant une plateforme d'apprentissage holistique conçue pour les étudiants de tous âges et de tous niveaux éducatifs. Notre plateforme fournit un soutien à l'apprentissage pour une large gamme de sujets, y compris les STEM, les sciences sociales et les langues, et aide également les étudiants à réussir divers tests et examens dans le monde entier, tels que le GCSE, le A Level, le SAT, l'ACT, l'Abitur, et plus encore. Nous proposons une bibliothèque étendue de matériels d'apprentissage, y compris des flashcards interactives, des solutions de manuels scolaires complètes et des explications détaillées. La technologie de pointe et les outils que nous fournissons aident les étudiants à créer leurs propres matériels d'apprentissage. Le contenu de StudySmarter est non seulement vérifié par des experts, mais également régulièrement mis à jour pour garantir l'exactitude et la pertinence.
En savoir plus
