Le raisonnement par récurrence

2.1 Vérifier ne suffit pas

Pour chaque entier $n$, calculons $n^2 - n + 41$. On obtient $41$, $41$, $43$, $47$, $53$, $61$… et ainsi de suite jusqu'à $n = 40$ : ces $41$ nombres sont tous premiers. Pourtant, pour $n = 41$ : $41^2 - 41 + 41 = 41^2 = 1\,681,$ qui n'est pas premier. Vérifier un grand nombre de cas ne démontre rien. Pour prouver qu'une propriété est vraie pour tous les entiers, il faut un raisonnement.

2.2 Le principe de récurrence

Principe. Soit $\mathcal{P}(n)$ une propriété qui dépend d'un entier naturel $n$, et $n_0$ un entier naturel. Si :

1. Initialisation : $\mathcal{P}(n_0)$ est vraie ;
2. Hérédité : pour tout entier $n \geq n_0$, si $\mathcal{P}(n)$ est vraie, alors $\mathcal{P}(n+1)$ est vraie ;

alors $\mathcal{P}(n)$ est vraie pour tout entier $n \geq n_0$.

L'image des dominos. L'initialisation fait tomber le premier domino. L'hérédité garantit que chaque domino qui tombe fait tomber le suivant. Alors $\mathcal{P}(n_0)$ entraîne $\mathcal{P}(n_0 + 1)$, qui entraîne $\mathcal{P}(n_0 + 2)$, et ainsi de suite : tous les dominos tombent.

Ce que dit vraiment l'hérédité. On ne suppose pas que $\mathcal{P}(n)$ est vraie pour tout $n$ (ce serait supposer ce qu'on veut démontrer). On montre une implication : pour un entier $n$ quelconque, si $\mathcal{P}(n)$ est vraie, alors $\mathcal{P}(n+1)$ l'est aussi.

2.3 Rédiger une récurrence

Une récurrence se rédige en quatre temps.

1. Énoncer la propriété : « Pour tout entier $n \geq n_0$, on note $\mathcal{P}(n)$ : … »
2. Initialisation : vérifier que $\mathcal{P}(n_0)$ est vraie.
3. Hérédité : « Soit $n \geq n_0$ un entier tel que $\mathcal{P}(n)$ est vraie. Montrons que $\mathcal{P}(n+1)$ est vraie. » L'affirmation « $\mathcal{P}(n)$ est vraie » s'appelle l'hypothèse de récurrence : on a le droit de s'en servir.
4. Conclusion : « Par récurrence, $\mathcal{P}(n)$ est vraie pour tout entier $n \geq n_0$. »

2.4 Un premier exemple

Exemple 6. Montrer que, pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.

Pour $n \in \mathbb{N}$, on note $\mathcal{P}(n)$ : « $4^n - 1$ est divisible par $3$ ».

Initialisation. $4^0 - 1 = 0 = 3 \times 0$ : $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}$ tel que $\mathcal{P}(n)$ est vraie : il existe un entier $k$ tel que $4^n - 1 = 3k$, c'est-à-dire $4^n = 3k + 1$. Alors $4^{n+1} - 1 = 4 \times 4^n - 1 = 4(3k + 1) - 1 = 12k + 3 = 3(4k + 1).$ Comme $4k + 1$ est un entier, $4^{n+1} - 1$ est divisible par $3$ : $\mathcal{P}(n+1)$ est vraie.

Conclusion. Pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$. (Premières valeurs : $0$, $3$, $15$, $63$.)

2.5 Les deux étapes sont indispensables

Sans initialisation, l'hérédité ne prouve rien. Prenons $\mathcal{P}(n)$ : « $4^n + 1$ est divisible par $3$ ». Elle est héréditaire : si $4^n + 1 = 3k$, alors $4^{n+1} + 1 = 4(4^n + 1) - 3 = 4 \times 3k - 3 = 3(4k - 1).$ Mais $4^0 + 1 = 2$ n'est pas divisible par $3$. En fait, $\mathcal{P}(n)$ est fausse pour tout $n$ : d'après l'exemple 6, $4^n - 1$ est un multiple de $3$, donc $4^n + 1 = (4^n - 1) + 2$ a pour reste $2$ dans la division par $3$.

Sans hérédité, vérifier des cas ne suffit pas : c'est l'exemple de $n^2 - n + 41$ (paragraphe 2.1).

2.6 Un peu d'histoire

Le raisonnement par récurrence est très ancien. On en trouve des formes vers l'an 1000 chez al-Karaji, puis au XIIᵉ siècle chez as-Samaw'al, deux mathématiciens de langue arabe, et au XVIᵉ siècle chez Maurolico. Pascal l'emploie au XVIIᵉ siècle dans son Traité du triangle arithmétique. À la fin du XIXᵉ siècle, Peano en fait l'un des principes de base des nombres entiers.