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

Général
Résumé Chapitre entier
Points théoriques
Preuve directe Preuve par contraposition Preuve par l'absurde Preuve par récurrence
Exercices
Exercice 1 Exercice 2 Exercice 3 Exercice 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.