Le raisonnement par récurrence

Principe de récurrence

Le raisonnement par récurrence permet de démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n$ à partir d'un certain rang $n_0$, souvent utilisé pour étudier des suites définies par une relation $u_{n+1} = f(u_n)$.

Principe de récurrence : pour démontrer que $P(n)$ est vraie pour tout entier $n \geqslant n_0$, on procède en trois étapes :

1. Initialisation : on vérifie que $P(n_0)$ est vraie.

2. Hérédité : on suppose que $P(n)$ est vraie pour un entier $n \geqslant n_0$ quelconque (hypothèse de récurrence), et on démontre qu'alors $P(n+1)$ est vraie aussi.

3. Conclusion : d'après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \geqslant n_0$.

Exemple détaillé

Soit la suite définie par $u_0 = 1$ et $u_{n+1} = 2u_n + 1$. Démontrons que pour tout entier $n$, $u_n \geqslant 0$ (propriété $P(n)$).

Initialisation : $u_0 = 1 \geqslant 0$, donc $P(0)$ est vraie.

Hérédité : supposons $u_n \geqslant 0$ pour un certain $n$. Alors :

Donc $P(n+1)$ est vraie.

Conclusion : par récurrence, $u_n \geqslant 0$ pour tout entier $n$.

Point de vigilance : il ne faut JAMAIS oublier l'étape d'initialisation : une hérédité vraie sans initialisation ne prouve rien (l'édifice entier "s'effondre" s'il n'a pas de premier étage).

Récurrence et monotonie de suites

On utilise souvent la récurrence pour prouver qu'une suite est croissante, décroissante, ou bornée, ce qui permet ensuite (avec le théorème de convergence monotone, admis) de justifier sa convergence.