Prérequis
Résumé
Ce chapitre reprend les techniques de base de résolutions de problèmes : des exemples de preuve directe, preuve par contraposition, preuve par l'absurde et preuve par récurrence sont donnés. Maîtriser ces différentes méthodes est primordial pour comprendre des preuves et en produire soi-même.
Ce chapitre a été
écrit par N. Radu et
mis en ligne le 8 décembre 2014.
1. Preuve directe
L'essentiel des assertions mathématiques sont de la forme $P \Rightarrow Q$, en ce sens que l'on possède une (ou plusieurs) hypothèse(s) $P$ et que l'on désire montrer la thèse $Q$.
La technique la plus naturelle pour démontrer une telle assertion est la preuve directe. Elle consiste simplement à supposer que $P$ est vrai, à faire des déductions logiques à partir de cette hypothèse et à parvenir à montrer que $Q$ est vrai.
Solution
Supposons que $x$ et $y$ soient effectivement des nombres impairs. Il existe donc des entiers $k$ et $l$ tels que
$$x = 2k+1 \quad \text{et} \quad y = 2l+1.$$ On a alors
$$x+y = 2k+1+2l+1 = 2k+2l+2 = 2(k+l+1),$$ ce qui montre que $x+y$ est un nombre pair.
2. Preuve par contraposition
Nous avons vu dans le chapitre sur la logique que la proposition $P \Rightarrow Q$ à laquelle nous nous intéressons est équivalente à $\lnot Q \Rightarrow \lnot P$. Une preuve par contraposition consiste à démontrer que l'on a $\lnot Q \Rightarrow \lnot P$, c'est-à-dire que si $Q$ est faux, alors $P$ également. On utilise cette méthode lorsque l'hypothèse $P$ semble difficile à exploiter ou lorsqu'on ne voit pas comment il sera possible de parvenir à la thèse $Q$.
Lorsque l'hypothèse ou la thèse contient une négation comme c'est le cas ici ($\neq$ est la négation de $=$), la preuve par contraposition est souvent une option à envisager.
Solution
Supposons que l'on a $f(x) = f(y)$ et montrons qu'alors $x = y$. On a
$$mx + n = my+n,$$ d'où
$$m(x-y) = 0$$ et, comme $m \neq 0$, on a $x = y$ comme espéré.
3. Preuve par l'absurde
La preuve par l'absurde, aussi appelée preuve par contradiction, se rapproche assez de la preuve par contraposition (et il n'y a parfois pas de réelles différences entre les deux). Elle consiste, lorsqu'on veut montrer que $P \Rightarrow Q$, à supposer que $P$ est vrai mais que $Q$ est faux, et à trouver une contradiction. Là aussi, cette technique peut servir lorsque la thèse $Q$ semble compliquée à démontrer directement. Il est alors plus simple de supposer que $Q$ n'est pas vérifié.
Solution
On suppose que $p$ est un nombre premier mais que sa racine carrée $\sqrt p$ n'est pas irrationnelle, c'est-à-dire qu'elle est rationnelle. On note alors $\displaystyle \sqrt{p} = \frac{a}{b}$ (où il s'agit d'une fraction irréductible) et on en déduit que
$$\begin{align}
& p = \frac{a^2}{b^2}\\[1mm]
\Leftrightarrow \ & pb^2 = a^2
\end{align}$$ Il suit que $a^2$ est divisible par $p$ et, comme $p$ est premier, cela implique que $a$ est lui-même divisible par $p$. On note alors $a = pa'$ avec $a' \in \mathbb{Z}$ et on a
$$\begin{align}
& pb^2 = p^2 a'^2\\[1mm]
\Leftrightarrow \ & b^2 = p a'^2
\end{align}$$ À nouveau, cela signifie que $b^2$ est divisible par $p$, et par conséquent $b$ également. Les nombres $a$ et $b$ sont donc tous les deux divisibles par $p$, ce qui est absurde car nous avions supposé que la fraction $\displaystyle \frac{a}{b}$ était irréductible.
4. Preuve par récurrence
Nous distinguons ici la récurrence simple de la récurrence forte, qui en est une généralisation.
Récurrence simple
Une preuve par récurrence se base sur le résultat suivant :
Principe de récurrence simple
Pour chaque $n \in \mathbb{N}_0$, soit $P(n)$ une affirmation mathématique. Si on a les deux propriétés :
- $P(1)$ est vrai,
- Pour tout $k \in \mathbb{N}_0$, si $P(k)$ est vrai alors $P(k+1)$ est vrai,
alors pour chaque $n \in \mathbb{N}_0$, l'affirmation $P(n)$ est vraie.
On peut envisager la récurrence lorsque l'on désire montrer une affirmation mathématique $P(n)$ dépendant d'un certain paramètre naturel $n$. On procède alors en deux étapes :
- L'initialisation : on montre que $P(1)$ est vrai.
- L'induction : on suppose que $P(k)$ est vrai pour un certain naturel $k$, et on montre que $P(k+1)$ est alors également vrai.
Solution
On procède par récurrence sur $n$ :
- Pour $n = 1$, on a effectivement
$$1 + q = \frac{1-q^2}{1-q}.$$
- Supposons que la formule soit vraie pour $n = k$ et montrons qu'elle l'est alors également pour $n = k+1$. On a
$$1+q+q^2 + \ldots + q^k = \frac{1 - q^{k+1}}{1-q}$$ et on peut donc en conclure que
$$\begin{align}
1+q+q^2 + \ldots + q^k + q^{k+1} &= \frac{1 - q^{k+1}}{1-q} + q^{k+1}\\[1mm]
&= \frac{1-q^{k+1} + q^{k+1}(1-q)}{1-q}\\[1mm]
&= \frac{1-q^{k+1}+q^{k+1} - q^{k+2}}{1-q}\\[1mm]
&= \frac{1-q^{k+2}}{1-q}
\end{align}$$ ce qui est exactement la formule pour $n = k+1$.
Récurrence forte
La récurrence forte se base quant à elle sur le résultat suivant, légèrement différent :
Principe de récurrence forte
Pour chaque $n \in \mathbb{N}_0$, soit $P(n)$ une affirmation mathématique. Si on a les propriétés
- $P(1)$ est vrai,
- Pour tout $k \in \mathbb{N}_0$, si $P(j)$ est vrai pour tout $j \in \{1, \ldots, k\}$ alors $P(k+1)$ est vrai,
alors pour chaque $n \in \mathbb{N}_0$, l'affirmation $P(n)$ est vraie.
On peut utiliser ce résultat pour effectuer une preuve par récurrence forte. Il s'agit du même raisonnement que la récurrence simple hormis que lors de l'étape d'induction, on peut supposer que $P(j)$ est vrai pour tout $j \in \{1, \ldots, k\}$. Dans certains cas, il n'est en effet pas possible de déduire $P(k+1)$ directement de $P(k)$, et il faut par exemple utiliser le fait que $P(k-1)$ ou $P(1)$ est vrai.