Les types de raisonnement avancés (Partie 2) 🤓

Ici, place à la cour des grands, on va s’attarder sur le raisonnement par l’absurde, les récurrences doubles et fortes, l’analyse synthèse ou encore l’obscur mais pas si dur Modus Ponens.

1. Raisonnement par l’absurde

Supposons que nous sommes face au problème suivant : étant donné un nombre rationnel et un nombre irrationnel, montrer que leur somme est irrationnelle.
Ici, un raisonnement direct semble compliqué à mettre en place, nous allons ruser un peu, prenons $a\in\mathbb{Q}$ et $b\in\mathbb{R}\backslash \mathbb{Q}$ et supposons par l’absurde que $c = a+b$ n’est PAS irrationnel (donc rationnel).

Ainsi, on peut réécrire notre inégalité comme suit : $b = c – a $, or la différence de deux nombres rationnels est rationnelle, on a donc réussi à prouver que $b$ était rationnel, c’est absurde avec les hypothèses que l’on a émise.
Ici, on a supposé quelque chose et on a abouti à une absurdité : cela signifie donc que notre hypothèse de base n’était pas bonne, donc la somme d’un irrationnel et d’un rationnel est effectivement irrationnelle. Ce type de raisonnement est ce que l’on appelle un raisonnement par l’absurde

Comme vous l’avez pu le voir dans l’exemple précédent, la preuve par l’absurde est une forme de preuve qui établit la vérité ou la validité d’une proposition en montrant que le fait de supposer que la proposition est fausse conduit à une contradiction.

Une preuve mathématique utilisant la preuve par l’absurde (ou par contradiction) se déroule généralement comme suit :

1. La proposition à prouver est $P$.
2. On suppose que P est fausse, c’est-à-dire qu’on suppose ¬P.
3. On montre ensuite que ¬P implique l’absurdité. Pour ce faire, on déduit généralement de l’hypothèse deux assertions mutuellement contradictoires, $Q$ et et son opposé $\not Q$, et on fait appel à la consistance des mathématiques (qui traduit le fait qu’on ne peut pas prouver à la fois un énoncé et son opposé).
4. Puisque supposer que P est fausse conduit à une contradiction, on conclut que P est en fait vraie.

Voici un premier exemple :

Résoudre l’inéquation $ dfrac{x^2-5x+6}{x-1} > 0$ sur $mathbb{R}$.

Faites le avant de voir comment on résoud cet exemple 😉

Question flash ⚡️

$\sqrt{2}$ est il rationnel ?

Une fois n’est pas coutume, pour prouver cela, supposons par l’absurde que $\sqrt{2}$ est rationnel. (étape 2)

⚠️POINT RAPPEL⚠️
Un nombre rationnel peut toujours s’écrire $\frac{p}{q}$ avec $q>0$ et $p,q$ premiers entre eux ! (En effet, s’ils ne sont pas premiers entre eux, on peut diviser numérateur et dénominateur par leur PGCD)

Soit alors $p,q\in\mathbb{Z}$ premiers entre eux tels que $\sqrt{2} = \frac{p}{q}$.
En élevant au carré et en multipliant par $q^2$, cette équation devient $2q^2=p^2$.
Or, on a prouvé (essayez de le refaire si vous ne savez plus comment faire !) dans le précédent chapitre que si $p^2$ est pair, alors $p$ l’est. Ainsi, on peut écrire $p=2p’$, d’où $q^2=2p’^2$ donc $q^2$ est pair, cela signifie que $q$ est aussi pair.

$p$ et $q$ ne sont donc pas premiers entre eux car divisibles par 2, c’est absurde ! (étape 3)
On a supposé que $\sqrt{2}$ était rationnel et on est tombé sur une contradiction, cela signifie donc que $\sqrt{2}$ est irrationnel !

2. Récurrence double et forte

Dans cette partie, nous allons généraliser le raisonnement par récurrence que l’on vous a présenté en début de chapitre. J’ai nommé : la récurrence double et la récurrence forte. Celles ci peuvent s’avérer très utile dans certaines situations. Pour aborder cette partie, je vous conseille d’être d’abord assez à l’aise avec le raisonnement par récurrence classique.

Petit aparté formalisme :

Le principe de récurrence simple se formule mathématiquement de la sorte :

$$\left[ \mathcal{P}(0) \wedge \left(\forall n\in\mathbb{N}, (\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1))\right)\right] \rightarrow \left(\forall n\in\mathbb{N}, \mathcal{P}(n)\right)$$

Essayez de prendre le temps de comprendre cette formule, et pourquoi elle n’est que reformulation du principe de récurrence !

Je vous met ci dessous les formulations mathématiques des récurrences double et forte, voyons si vous arriverez à comprendre leur principe avant d’aller lire la suite du cours !

$$\left[ \mathcal{P}(0) \wedge \mathcal{P}(1) \wedge \left(\forall n\in\mathbb{N}, (\mathcal{P}(n) \wedge \mathcal{P}(n+1) \Rightarrow \mathcal{P}(n+2))\right)\right] \rightarrow \left(\forall n\in\mathbb{N}, \mathcal{P}(n)\right)$$

$$\left[ \mathcal{P}(0) \wedge \left(\forall n\in\mathbb{N}^*, (\mathcal{P}(0) \wedge \mathcal{P}(1) \wedge \cdots \wedge \mathcal{P}(n-1) \Rightarrow \mathcal{P}(n))\right)\right] \rightarrow \left(\forall n\in\mathbb{N}, \mathcal{P}(n)\right)$$

A- La récurrence double

Intuitivement, une propriété que l’on démontre par récurrence est une propriété dont la véracité se “propage” d’un rang à l’autre. On commence donc par démontrer qu’elle est vraie quelque part (il s’agit de l’étape d’initialisation, puis on démontre qu’elle vérifie la propriété de “propagation”𝑛 : c’est à dire que si elle est vaie à un rang, alors elle l’est aussi au rang suivant (c’est l’hérédité). Ceci permet de conclure qu’une telle propriété est vraie pour tous les rangs suivant le rang d’initialisation.

Le principe de la récurrence double n’est pas beaucoup plus dur que celui de la récurrence simple : pour l’hérédité, au lieu d’utiliser uniquement le terme précédent, on va utiliser les deux termes précédents. La conséquence logique sur l’initialisation est qu’on va devoir vérifier la propriété sur les deux premiers termes. Elle permet de démontrer des propriétés dont la véracité ne se “propage” pas directement d’un rang au rang suivant, mais dont la véracité à un rang donné dépend de sa véracité aux deux rangs précédents.

Voici le principe de la récurrence double :
– Initialisation : La propriété est vraie pour un rang $n_0$ et pour le suivant $n_0+1$ (généralement, ces deux rangs seront $0$ et $1$).
– Hérédité : On suppose que pour un entier $n\geq n_0$ donné, la propriété est vraie au rang $n$ et au rang $n+1$, on prouve alors la propriété au rang $n+2$.
– Conclusion : écrire une phrase du type “par récurrence double, pour tout $n\geq n_0,$ la propriété $\mathcal{P}(n)$ est vraie.”

Question flash ⚡️

Que peut on prouver (par récurrence double) à propos de la suite de Fibonacci : pour rappel, il s’agit de la suite telle que $F_0 = 0, F₁ = 1$ et pour $n\in\mathbb{N}, F_{n+2} = F_{n+1}+F_n$. (plusieurs bonnes réponses possibles)

Passons à un petit exemple pour avoir un exemple de démonstration pour la récurrence double.

Exemple :

Considérons la suite définie par récurrence par : $u_0=1, u_1=3, u_{n+2} = 4u_{n+1}- 3u_n $
Montrer que pour tout $n\in\mathbb{N}$, $u_n = 3^n$.

Montrons par récurrence double la propriété suivante : $\mathcal{P}(n):$ « $u_n = 3^n$ ».
Initialisation : $u_0=1=3^0$ et $u_1=3=3^1$. La propriété est donc vraie aux rangs $n=0$ et $n=1$.
Hérédité : Soit $n\in\mathbb{N}$, supposons que la propriété est vraie au rang $n$ et $n+1$.
Prouvons la au rang $n+2$ :
$u_{n+2} = 4u_{n+1}-3u_n = 4\cdot 3^{n+1} – 3\cdot 3^n = (4-1)\cdot 3^{n+1} = 3\cdot 3^{n+1} = 3^{n+2}$.
La propriété est héréditaire, donc par récurrence double on a prouvé que $u_n = 3^n \forall n\in\mathbb{N}$.

B- La récurrence forte

On a vu que la récurrence simple permet de démontrer des propriétés qui se “propagent” d’un rang au rang suivant, la récurrence double permet de démontrer des propriétés dont la véracité à un rang donné se déduit de sa véracité aux deux rangs précédents. La récurrence forte, elle, nous permettra de démontrer des propriétés où il faut supposer la véracité de tous les rangs précédents pour prouver la véracité à un certain rang.

Cette fois, la différence de rédaction par rapport à la récurrence simple ne réside que dans les hypothèses supplémentaires que l’on peut faire lors de l’hérédité.

Voici le principe de la récurrence forte :
– Initialisation : La propriété est vraie pour un rang $n_0$ (généralement $0$).
– Hérédité : On suppose que pour un entier $n\geq n_0$ donné, la propriété est vraie aux rangs $n_0 \leq k \leq n$, on prouve alors la propriété au rang $n+1$.
– Conclusion : écrire une phrase du type “par récurrence forte, pour tout $n\geq n_0,$ la propriété $\mathcal{P}(n)$ est vraie.”

Exemple :

Théorème : Montrer que tout entier naturel $n \geq 2$ s’écrit comme produit de nombres premiers.

⚠️POINT RAPPEL⚠️
Un nombre premier est un entier naturel qui n’admet que 2 diviseurs distincts : lui même et 1.
Les nombres $0$ et $1$ ne sont pas des nombres premiers (car ils ont respectivement une infinité de diviseurs et un seul diviseur)
Les nombres $2,3,5,7,11$ sont des nombres premiers.
$4$ n’est pas premier, car divisible par $1,2$ et $4$.

Au collège, vous avez admis ce théorème, nous allons dès à présent le prouver à l’aide du principe de récurrence forte !

Cet exercice peut sembler difficile à appréhender, mais grâce à la récurrence forte, il ne nous posera aucun problème, notons donc, pour $n\geq 2, \mathcal{P}(n) : “n$ s’écrit comme produit de nombres premiers”.

Initialisation : Prouvons $\mathcal{P}(2)$ : $2$ est un nombre premier, et $2=2$, donc $2$ s’écrit bien comme produit d’un seul nombre premier.

Hérédité : Soit $n\geq 2$, supposons que pour $2\leq k \leq n$, la propriété $\mathcal{P}(k)$ est vraie.
Montrons que $n+1$ s’écrit alors comme produit de nombres premiers. On se retrouve face à deux cas : (cela vous rappelle un raisonnement 😄?)
– Cas 1 : $n+1$ est un nombre premier, donc $n+1 = n+1$ est une écriture en produits de nombres premiers de $n+1$.
– Cas 2 : $n+1$ n’est pas un nombre premier, donc il existe $k\neq 1$ et $\neq n+1$ tel que $k$ divise $n+1$. On a alors $2\leq \frac{n+1}{k}$ et $2\leq k$, ces deux nombres admettent une décomposition en produits de nombres premiers par hypothèse de récurrence forte

Voici un petit exercice mêlant disjonction de cas et équivalence !

C- Contraposée

Le raisonnement par contraposée permet de démontrer qu’une implication du type ‘$PRightarrow Q$’ est vraie. Ce raisonnement se base sur l’équivalence entre l’assertion ‘$PRightarrow Q$’ et l’assertion ‘non $Q Rightarrow$ non $P $’. Donc si l’on souhaite montrer l’assertion $PRightarrow Q$, on montre en faite que si non $Q$ est vraie alors non $P$ est vraie.

Un petit exemple en français pour vous convaincre de la véracité de cette propriétés, normalement vous devriez être convaincus que les deux phrases suivantes sont équivalentes :
(1) – S’il pleut, je mets mon parapluie
(2) – Si je ne mets pas mon parapluie, il ne pleut pas.

Question flash ⚡️

Si l’on se place dans le formalisme avec les $P$ et les $Q$, en considérant que la phrase (1) représente $PRightarrow Q$ et (2) représente $neg Q Rightarrow negP$, quelle groupe de mot prend la place de $P$ ?

Un exercice très classique où il est judicieux de raisonner par contraposée est le suivant :

Soit $ninmathbb{N}$, montrer que si $n^2$ est pair, alors $n$ est pair.

Raisonnons par contraposée : montrons que si $n$ n’est pas pair (donc impair), alors $n^2$ n’est pas pair (donc impair) :

Soit $ninmathbb{N}$ un entier impair, il existe $k$ entier tel que $n=2k+1$. Alors, $n^2=(2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1$ : $n^2$ est bien impair, donc on a prouvé par contraposée que si $n^2$ est pair, alors $n$ l’est aussi !

Dans le prochain cours, on découvrira des types de raisonnement un peu plus évolués, accrochez vous ça va secouer !