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

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 :

Pour chaque $n \in \mathbb{N}_0$, soit $P(n)$ une affirmation mathématique. Si on a les deux propriétés :
  1. $P(1)$ est vrai,
  2. 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}.$$
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 :

Pour chaque $n \in \mathbb{N}_0$, soit $P(n)$ une affirmation mathématique. Si on a les propriétés
  1. $P(1)$ est vrai,
  2. 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.