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 :

u_{n+1} = 2u_n + 1 \geqslant 2\times 0 + 1 = 1 \geqslant 0

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.

Exercices de la leçon

Exercice 1

Dans un raisonnement par récurrence, l'étape d'initialisation consiste à :

Corrigé

L'initialisation vérifie que la propriété est vraie au rang de départ $n_0$ , point de départ indispensable du raisonnement.

Exercice 2

On peut conclure qu'une propriété est vraie pour tout $n$ si seule l'étape d'hérédité a été démontrée, sans initialisation.

Corrigé

Sans l'initialisation, le raisonnement par récurrence n'est pas valide : il faut un premier rang vérifié pour que la chaîne d'implications démarre.

Exercice 3

Démontre par récurrence que pour tout entier naturel $n$ , $2^n \geqslant n+1$ .

Corrigé

On applique scrupuleusement les trois étapes : initialisation au rang 0, hérédité en utilisant l'hypothèse de récurrence pour majorer $2^{n+1}$ , puis conclusion.

Exercice 4

Soit $(u_n)$ définie par $u_0 = 2$ et $u_{n+1} = \dfrac{1}{2}u_n + 1$ . Démontre par récurrence que pour tout $n$ , $u_n \leqslant 2$ .

Corrigé

On utilise l'hypothèse de récurrence $u_n \leqslant 2$ pour majorer directement $u_{n+1}$ par composition avec la fonction affine croissante $x \mapsto \frac{1}{2}x+1$ .

Exercice 5

Soit $(u_n)$ définie par $u_0=1$ et $u_{n+1}=u_n+2n+1$ . Quelle formule explicite peut-on conjecturer puis démontrer par récurrence ?

Corrigé

On calcule les premiers termes : $u_0=1$ , $u_1=u_0+2(0)+1=2$ , $u_2=u_1+2(1)+1=5$ , $u_3=u_2+2(2)+1=10$ . La suite $1,2,5,10$ correspond à $n^2+1$ ( $0^2+1=1$ , $1^2+1=2$ , $2^2+1=5$ , $3^2+1=10$ ). On vérifie l'hérédité : si $u_n=n^2+1$ alors $u_{n+1}=n^2+1+2n+1=(n+1)^2+1$ , ce qui confirme la formule par récurrence.

AlphaMath Académie · Le raisonnement par récurrence · Limites de suites et raisonnement par récurrence