Raisonnement par contraposée, disjonction de cas, récurrence

Trois outils pour prouver : retourner une implication (contraposée), découper le problème en cas qui couvrent tout (disjonction de cas), ou faire tomber une file de dominos (récurrence).

Objectifs

Écrire la contraposée d'une implication et ne pas la confondre avec la réciproque.
Démontrer une propriété en séparant tous les cas possibles.
Rédiger une démonstration par récurrence complète : initialisation, hérédité, conclusion.
Choisir le type de raisonnement adapté à un énoncé.

1. Le raisonnement par contraposée

Notions clés

Soient \(P\) et \(Q\) deux propositions. L'implication \(P \Rightarrow Q\) signifie : « chaque fois que \(P\) est vraie, \(Q\) est vraie ».

Sa contraposée est \(\text{non}\,Q \Rightarrow \text{non}\,P\).
Sa réciproque est \(Q \Rightarrow P\).

Exemple résolu

Soit \(n\) un entier. Démontrer que : si \(n^2\) est pair, alors \(n\) est pair.

On écrit la contraposée : « si \(n\) est impair, alors \(n^2\) est impair ». C'est elle qu'on démontre.

Supposons \(n\) impair : il existe un entier \(k\) tel que \(n = 2k+1\).

On calcule : \[ n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. \]

\(2k^2+2k\) est un entier, donc \(n^2\) s'écrit \(2m+1\) : \(n^2\) est impair.

La contraposée est démontrée, donc l'implication de départ aussi : si \(n^2\) est pair, alors \(n\) est pair.

À toi de jouer

Soit \(x\) un réel. Démontrer que : si \(x^2 \neq 9\), alors \(x \neq 3\).

Voir la solution

La contraposée est : « si \(x = 3\), alors \(x^2 = 9\) ». Or si \(x = 3\), \(x^2 = 3^2 = 9\). La contraposée est vraie, donc l'implication aussi.

Quelle est la contraposée de « Si Fatou a son bac, alors elle va à l'université » ?

Si Fatou va à l'université, alors elle a son bac.
Si Fatou n'a pas son bac, alors elle ne va pas à l'université.
Si Fatou ne va pas à l'université, alors elle n'a pas son bac.

On nie la conclusion et on la met en hypothèse : non Q implique non P. La réponse 1 est la réciproque, la réponse 2 est la réciproque de la contraposée (elle n'est pas forcément vraie).

2. Le raisonnement par disjonction de cas

Notions clés

Pour démontrer une propriété, on sépare la situation en plusieurs cas qui couvrent toutes les possibilités, puis on démontre la propriété dans chaque cas.

Un entier \(n\) est pair (\(n = 2k\)) ou impair (\(n = 2k+1\)).
Un réel \(x\) est positif ou négatif (utile avec la valeur absolue).
Le reste de la division d'un entier par 3 vaut 0, 1 ou 2 : \(n = 3k\), \(n = 3k+1\) ou \(n = 3k+2\).

flowchart LR
  A[Propriété à prouver pour tout n] --> B[Cas 1 n pair]
  A --> C[Cas 2 n impair]
  B --> D[Vraie dans le cas 1]
  C --> E[Vraie dans le cas 2]
  D --> F[Vraie pour tout n]
  E --> F

Exemple résolu

Démontrer que, pour tout entier \(n\), le produit \(n(n+1)\) est pair.

Tout entier est pair ou impair : on étudie ces deux cas, qui couvrent tout.

Cas 1 : \(n\) pair, \(n = 2k\). Alors \(n(n+1) = 2k(2k+1) = 2\big(k(2k+1)\big)\) est pair.

Cas 2 : \(n\) impair, \(n = 2k+1\). Alors \(n+1 = 2k+2\) et \[ n(n+1) = (2k+1)(2k+2) = 2(2k+1)(k+1), \] qui est pair.

Dans tous les cas, \(n(n+1)\) est pair.

À toi de jouer

Démontrer que, pour tout entier \(n\), le reste de la division de \(n^2\) par 3 vaut 0 ou 1 (jamais 2).

Voir la solution

On distingue les trois restes possibles de \(n\) dans la division par 3.

\(n = 3k\) : \(n^2 = 9k^2 = 3(3k^2)\), reste 0.
\(n = 3k+1\) : \(n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1\), reste 1.
\(n = 3k+2\) : \(n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1\), reste 1.

Dans les trois cas, le reste vaut 0 ou 1.

Pour démontrer que \(|x - 2| + |x + 2| \geq 4\) pour tout réel \(x\), quels cas faut-il étudier ?

\(x \geq 0\) et \(x < 0\)
\(x < -2\), puis \(-2 \leq x \leq 2\), puis \(x > 2\)
\(x = 2\) et \(x = -2\)

Les valeurs absolues changent d'expression en \(-2\) et en \(2\) : il faut trois intervalles qui couvrent tous les réels. Deux valeurs isolées ne couvrent pas tous les réels.

3. Le raisonnement par récurrence

On pousse le premier domino : on vérifie que la propriété est vraie au premier rang (initialisation).

Chaque domino qui tombe fait tomber le suivant : on montre que si la propriété est vraie à un rang n, elle l'est au rang n+1 (hérédité).

Les deux conditions réunies font tomber toute la file : la propriété est vraie à tous les rangs (conclusion).

Notions clés

Soit \(P(n)\) une propriété qui dépend d'un entier naturel \(n\), et \(n_0\) un entier naturel. Si :

Initialisation : \(P(n_0)\) est vraie ;
Hérédité : pour tout entier \(n \geq n_0\), si \(P(n)\) est vraie, alors \(P(n+1)\) est vraie ;

alors \(P(n)\) est vraie pour tout entier \(n \geq n_0\) (conclusion).

Exemple résolu 1 : une somme

Démontrer que, pour tout entier \(n \geq 1\) : \[ 1 + 2 + \dots + n = \frac{n(n+1)}{2}. \]

On note \(P(n)\) : « \(1 + 2 + \dots + n = \frac{n(n+1)}{2}\) ».

Initialisation (\(n = 1\)) : à gauche on a \(1\), à droite \(\frac{1 \times 2}{2} = 1\). Donc \(P(1)\) est vraie.

Hérédité : soit \(n \geq 1\) tel que \(P(n)\) est vraie. Alors \[ 1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1). \]

On factorise par \(n+1\) : \[ \frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2} + 1\right) = \frac{(n+1)(n+2)}{2}. \] C'est exactement \(P(n+1)\).

Conclusion : \(P(1)\) est vraie et la propriété est héréditaire, donc \(P(n)\) est vraie pour tout \(n \geq 1\). Par exemple \(1 + 2 + \dots + 100 = \frac{100 \times 101}{2} = 5050\).

Exemple résolu 2 : l'inégalité de Bernoulli

Soit \(a\) un réel strictement positif. Démontrer que, pour tout entier \(n \geq 0\) : \[ (1+a)^n \geq 1 + na. \]

Avant la preuve, observe : fais varier \(a\) et compare la courbe exponentielle \(y = (1+a)^x\) et la droite \(y = 1 + ax\) aux points d'abscisse entière.

Cherche d'abord l'hérédité, puis compare avec la correction.

Voir la solution

Initialisation (\(n = 0\)) : \((1+a)^0 = 1\) et \(1 + 0 \times a = 1\), donc \(1 \geq 1\) : vrai.

Hérédité : soit \(n \geq 0\) tel que \((1+a)^n \geq 1 + na\). Comme \(1 + a > 0\), on peut multiplier les deux membres par \(1+a\) sans changer le sens :

\[ \begin{aligned} (1+a)^{n+1} &\geq (1+na)(1+a) \\ &= 1 + a + na + na^2 \\ &= 1 + (n+1)a + na^2 \\ &\geq 1 + (n+1)a \quad \text{car } na^2 \geq 0. \end{aligned} \]

Conclusion : pour tout entier \(n \geq 0\), \((1+a)^n \geq 1 + na\).

À toi de jouer : une suite

La suite \((u_n)\) est définie par \(u_0 = 4\) et \(u_{n+1} = 2u_n - 3\). Démontrer que, pour tout \(n \geq 0\), \(u_n = 2^n + 3\).

Voir la solution

Initialisation : \(2^0 + 3 = 1 + 3 = 4 = u_0\). Vrai.

Hérédité : supposons \(u_n = 2^n + 3\) pour un entier \(n \geq 0\). Alors \[ u_{n+1} = 2u_n - 3 = 2(2^n + 3) - 3 = 2^{n+1} + 6 - 3 = 2^{n+1} + 3. \]

Conclusion : pour tout \(n \geq 0\), \(u_n = 2^n + 3\). Vérification : \(u_1 = 2 \times 4 - 3 = 5 = 2^1 + 3\).

Dans l'étape d'hérédité, que fait-on exactement ?

On suppose \(P(n)\) vraie pour un entier \(n\) fixé et on démontre \(P(n+1)\).
On suppose \(P(n)\) vraie pour tout \(n\) et on conclut.
On vérifie \(P(0)\), \(P(1)\) et \(P(2)\) puis on généralise.

L'hypothèse de récurrence porte sur un seul rang \(n\). Supposer la propriété vraie pour tout \(n\), c'est supposer le résultat ; vérifier quelques valeurs ne prouve rien pour les suivantes.

4. Quel raisonnement choisir ?

flowchart TD
  A[Énoncé à démontrer] --> B{Propriété pour tout entier n}
  B -->|Lien entre rangs successifs| C[Récurrence]
  B -->|Pair impair ou restes| D[Disjonction de cas]
  A --> E{Implication P vers Q}
  E -->|non Q plus simple que P| F[Contraposée]

Pour démontrer que \(5^n - 1\) est divisible par 4 pour tout entier naturel \(n\), quel raisonnement est le plus naturel ?

La contraposée
La récurrence
La disjonction de cas pair ou impair

On passe facilement du rang \(n\) au rang \(n+1\) : \(5^{n+1} - 1 = 5(5^n - 1) + 4\). Si \(5^n - 1 = 4k\), alors \(5^{n+1} - 1 = 4(5k + 1)\). Avec \(5^0 - 1 = 0\) divisible par 4, la récurrence conclut.

Erreurs fréquentes

Confondre contraposée (\(\text{non}\,Q \Rightarrow \text{non}\,P\)) et réciproque (\(Q \Rightarrow P\)).
Oublier un cas dans une disjonction de cas, ou choisir des cas qui ne couvrent pas tout.
Oublier l'initialisation dans une récurrence, ou initialiser au mauvais rang.
Dans l'hérédité, écrire « supposons \(P(n)\) vraie pour tout \(n\) » : c'est supposer ce qu'on veut démontrer.
Ne pas utiliser l'hypothèse de récurrence : si elle ne sert pas, l'hérédité est sûrement mal faite.

Récapitulatif

Contraposée : pour prouver \(P \Rightarrow Q\), on prouve \(\text{non}\,Q \Rightarrow \text{non}\,P\).
Disjonction de cas : on découpe en cas qui couvrent tout, on prouve chaque cas.
Récurrence : initialisation + hérédité, puis conclusion pour tout \(n \geq n_0\).

Contraposée de P ⇒ Q

non Q ⇒ non P, toujours équivalente à P ⇒ Q.

Réciproque de P ⇒ Q

Q ⇒ P, qui peut être fausse même si P ⇒ Q est vraie.

Disjonction de cas

Découper en cas couvrant toutes les possibilités et prouver chaque cas.

Initialisation

Vérifier que la propriété est vraie au premier rang n₀.

Hérédité

Supposer P(n) vraie pour un n fixé et démontrer P(n+1).