Le raisonnement par récurrence

4.1 Le principe

Pour démontrer qu'une propriété $\mathcal{P}(n)$, qui dépend d'un entier naturel $n$, est vraie pour tout entier $n \geq n_0$, on procède en deux étapes.

1. Initialisation : on vérifie que $\mathcal{P}(n_0)$ est vraie.
2. Hérédité : on suppose que $\mathcal{P}(n)$ est vraie pour un entier $n \geq n_0$ quelconque (c'est l'hypothèse de récurrence), et on démontre qu'alors $\mathcal{P}(n + 1)$ est vraie.

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

C'est l'image d'une échelle : on peut monter sur le premier barreau (initialisation), et de chaque barreau on peut monter sur le suivant (hérédité). On peut donc atteindre tous les barreaux.

4.2 Démontrer une formule

Exemple 18 (suite de l'exemple 3). Soit $v_0 = 0$ et $v_{n+1} = v_n + 2n + 1$. Montrons que $v_n = n^2$ pour tout $n \in \mathbb{N}$.

Pour $n \in \mathbb{N}$, on note $\mathcal{P}(n)$ : « $v_n = n^2$ ».

Initialisation. $v_0 = 0 = 0^2$ : $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}$ tel que $v_n = n^2$. Alors $v_{n+1} = v_n + 2n + 1 = n^2 + 2n + 1 = (n + 1)^2$ : $\mathcal{P}(n + 1)$ est vraie.

Conclusion. Pour tout $n \in \mathbb{N}$, $v_n = n^2$.

Comme $v_n = 1 + 3 + 5 + \cdots + (2n - 1)$ pour $n \geq 1$, on a aussi démontré que la somme des $n$ premiers nombres impairs vaut $n^2$. On le voit sur un carré de côté $n$ : on passe au carré de côté $n + 1$ en ajoutant une bande en équerre de $2n + 1$ petits carrés.

Exemple 19 (suite de l'exemple 2). Soit $u_0 = 1$ et $u_{n+1} = \dfrac12 u_n + 2$. Montrons que $u_n = 4 - \dfrac{3}{2^n}$ pour tout $n \in \mathbb{N}$.

Initialisation. $4 - \dfrac{3}{2^0} = 4 - 3 = 1 = u_0$.

Hérédité. Supposons $u_n = 4 - \dfrac{3}{2^n}$ pour un entier $n$. Alors $u_{n+1} = \frac12\left(4 - \frac{3}{2^n}\right) + 2 = 2 - \frac{3}{2^{n+1}} + 2 = 4 - \frac{3}{2^{n+1}}.$

Conclusion. Pour tout $n \in \mathbb{N}$, $u_n = 4 - \dfrac{3}{2^n}$. Par exemple $u_{10} = 4 - \dfrac{3}{1024} = \dfrac{4093}{1024} \approx 3{,}997$.

4.3 Démontrer une inégalité, un sens de variation

Exemple 20 (suite de l'exemple 2). Montrons que $u_n < 4$ pour tout $n$, sans utiliser la formule de l'exemple 19.

Initialisation. $u_0 = 1 < 4$.

Hérédité. Supposons $u_n < 4$. Alors $\dfrac12 u_n < 2$, donc $\dfrac12 u_n + 2 < 4$, c'est-à-dire $u_{n+1} < 4$.

Conclusion. $u_n < 4$ pour tout $n \in \mathbb{N}$.

Sens de variation. $u_{n+1} - u_n = 2 - \dfrac12 u_n = \dfrac12(4 - u_n) > 0$, puisque $u_n < 4$. La suite est strictement croissante. Elle est donc minorée par $u_0 = 1$, et $1 \leq u_n < 4$ : elle est bornée.

4.4 Les deux étapes sont indispensables

• Vérifier quelques cas ne suffit pas. Le nombre $n^2 + n + 41$ est premier pour $n = 0, 1, 2, \ldots, 39$, mais pas pour $n = 40$ : $40^2 + 40 + 41 = 1681 = 41^2$.
• L'hérédité seule ne suffit pas. Soit $\mathcal{P}(n)$ : « $4^n + 1$ est un multiple de $3$ ». Si $4^n + 1 = 3k$, alors $4^{n+1} + 1 = 4\left(4^n + 1\right) - 3 = 3(4k - 1)$ : l'hérédité est vraie. Pourtant $4^0 + 1 = 2$ n'est pas un multiple de $3$, et en fait $\mathcal{P}(n)$ est fausse pour tout $n$ ($4^n + 1$ vaut $2, 5, 17, 65, \ldots$).