Récurrence — Principe, étapes et exemples

La récurrence est une méthode de démonstration qui permet de montrer qu’un énoncé est vrai pour tout entier à partir d’une certaine valeur initiale. Pour prouver une affirmation pour tous les $n \ge n_0$, on montre que le premier cas est vrai, puis que la vérité à un entier entraîne la vérité à l’entier suivant.

Si ces deux parties sont correctes, l’énoncé est vrai pour tous les entiers de l’intervalle considéré. C’est toute l’idée.

Comment fonctionne la récurrence

Écrivez l’énoncé sous la forme $P(n)$. La récurrence suit alors cette structure :

1. Prouver le cas de base : montrer que $P(n_0)$ est vraie.
2. Prouver l’étape de récurrence : montrer que si $P(k)$ est vraie pour un entier arbitraire $k \ge n_0$, alors $P(k+1)$ est aussi vraie.

Une fois cela fait, on peut conclure que $P(n)$ est vraie pour tout entier $n \ge n_0$.

La logique est séquentielle. Le cas de base lance la chaîne, et l’étape de récurrence fait avancer la chaîne d’un entier à la fois.

Pourquoi le cas de base et l’étape de récurrence sont tous deux essentiels

Le cas de base fournit le premier énoncé vrai. L’étape de récurrence dit que la vérité se transmet d’un entier au suivant.

Donc si $P(n_0)$ est vraie, alors $P(n_0 + 1)$ est vraie. Puis $P(n_0 + 2)$ est vraie, et ainsi de suite. La récurrence ne saute ni le point de départ, ni le lien entre un cas et le suivant.

Exemple détaillé : démontrer une formule de somme par récurrence

Un exemple classique est la formule

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

pour tous les entiers $n \ge 1$.

Posons

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Cas de base

Prenons $n = 1$. Le membre de gauche vaut $1$, et le membre de droite vaut

$$\frac{1(1+1)}{2} = 1$$

Donc $P(1)$ est vraie.

Étape de récurrence

Supposons que $P(k)$ soit vraie pour un entier arbitraire $k \ge 1$. Cela signifie que

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Montrons maintenant $P(k+1)$. Partons du membre de gauche pour $k+1$ :

$$1 + 2 + 3 + \cdots + k + (k+1)$$

En utilisant l’hypothèse de récurrence,

$$\frac{k(k+1)}{2} + (k+1)$$

Mettons $(k+1)$ en facteur :

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Puis simplifions :

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

C’est exactement la formule avec $n = k+1$. Donc $P(k+1)$ est vraie.

Puisque le cas de base et l’étape de récurrence sont tous deux démontrés, la formule est vraie pour tous les entiers $n \ge 1$.

Quand utiliser la récurrence

La récurrence est utile lorsqu’un énoncé dépend d’un paramètre entier et que chaque cas est naturellement relié à un cas précédent. Cela arrive souvent avec les sommes, les énoncés de divisibilité, les inégalités, les relations de récurrence et les preuves d’algorithmes.

Commencez par identifier la bonne valeur initiale. Certaines affirmations commencent à $n = 0$, d’autres à $n = 1$, et d’autres encore n’ont de sens que pour des entiers plus grands.

Vérifiez ensuite quel est le cas valide suivant. L’étape habituelle va de $k$ à $k+1$, mais si l’énoncé ne concerne que les entiers pairs, une étape de $k$ à $k+2$ peut être la bonne version.

Erreurs fréquentes dans les preuves par récurrence

Prouver seulement le cas de base

Le cas de base vérifie uniquement la première valeur. À lui seul, il ne prouve pas l’énoncé pour les entiers suivants.

Utiliser une mauvaise valeur initiale

Si l’affirmation concerne tous les $n \ge 2$, prouver seulement $P(1)$ n’aide pas. Le cas de base doit correspondre à l’intervalle réel de l’énoncé.

Manipuler l’hypothèse de récurrence sans précaution

Dans l’étape de récurrence, on suppose $P(k)$ pour un entier arbitraire $k$ dans l’intervalle valide. On ne suppose pas que tout le théorème est déjà démontré.

Prouver le mauvais cas suivant

Si votre théorème exige une étape $k \to k+1$, démontrer une autre étape ne suffit pas, sauf si vous expliquez pourquoi cette autre étape est suffisante.

Une extension utile : la récurrence forte

Parfois, démontrer $P(k+1)$ demande plus que seulement $P(k)$. Dans ce cas, la récurrence forte permet de supposer tous les cas précédents jusqu’à $k$, puis de démontrer le suivant.

L’idée est très proche, mais l’hypothèse est plus forte. C’est utile, par exemple, lorsqu’une preuve dépend de la décomposition d’un nombre en parties plus petites.

Essayez votre propre version

Prenez l’affirmation

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

et démontrez-la pour tous les entiers $n \ge 1$ en utilisant la même structure : d’abord le cas de base, puis l’étape de $k$ à $k+1$. Si vous pouvez rédiger cette preuve proprement, la méthode devient généralement claire.