Théorie > Fondements > Techniques élémentaires de preuves

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.

Exemple
Montrer que si $x$ et $y$ sont des nombres impairs, alors $x+y$ est un nombre pair.

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$.

Exemple
Soit $m,n \in \mathbb R$ avec $m \neq 0$ et $f : \mathbb{R} \to \mathbb{R}$ la fonction définie par $f(x) = mx+n$. Montrer que si $x \neq y$, alors $f(x) \neq f(y)$.

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é.

Exemple
Montrer que la racine carrée d'un nombre premier est un nombre irrationnel.

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 :
  1. L'initialisation : on montre que $P(1)$ est vrai.
  2. 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.

Exemple
Montrer que pour tout $q \in \mathbb{R} \setminus \{1\}$ et tout $n \in \mathbb{N}_0$, on a
$$1+q+q^2 + \ldots + q^n = \frac{1 - q^{n+1}}{1-q}.$$

Solution
On procède par récurrence sur $n$ :
  1. Pour $n = 1$, on a effectivement
    $$1 + q = \frac{1-q^2}{1-q}.$$
  2. 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$.

Remarque
On peut procéder par récurrence tout en utilisant également une des méthodes précédentes (par contraposition ou par l'absurde). En effet, pour montrer $P(k+1)$ en partant des hypothèses (à savoir $P(k)$ et les hypothèses supplémentaires du problème), on peut par exemple supposer que $P(k+1)$ est faux et chercher une contradiction.

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.

Remarque
Si, en essayant de faire une récurrence simple, on se rend compte qu'on a besoin de $P(k-1)$ pour montrer $P(k+1)$, alors on peut simplement la transformer en récurrence forte. Toutefois, il ne faut pas oublier dans ce cas précis qu'on aura un problème pour déduire $P(2)$ à partir de $P(1)$ ! Il faut alors rajouter dans le cas de base la démonstration de $P(2)$ (éventuellement en utilisant $P(1)$). De manière générale, si lors d'une induction on a besoin de $P(k-\alpha)$ pour montrer $P(k+1)$ (pour un certain $\alpha$ fixé), alors il sera nécessaire de montrer $P(1), P(2), \ldots, P(\alpha+1)$ séparément dans le cas de base.