Démonstration par récurrence : la méthode en 3 étapes

Le rituel en 3 étapes

Pour démontrer qu’une propriété $P(n)$ est vraie pour tout entier $n \geq n_0$ :

Étape 1 : Initialisation

Vérifier que $P(n_0)$ est vraie (souvent $n_0 = 0$ ou $1$).

Étape 2 : Hérédité

Supposer $P(n)$ vraie pour un $n \geq n_0$ fixé (hypothèse de récurrence). Prouver que $P(n + 1)$ est vraie.

Étape 3 : Conclusion

Par récurrence, $P(n)$ est vraie pour tout $n \geq n_0$.

Exemple : $\displaystyle \sum_{k=1}^n k = \dfrac{n(n+1)}{2}$

Notons $P(n)$ : $1 + 2 + \ldots + n = \dfrac{n(n+1)}{2}$.

Initialisation ($n = 1$) : $1 = 1 \cdot 2 / 2 = 1$. ✓

Hérédité : Supposons $P(n)$ vraie. Montrons $P(n+1)$.

$1 + 2 + \ldots + n + (n+1) = \dfrac{n(n+1)}{2} + (n+1) = (n+1) \left( \dfrac{n}{2} + 1 \right) = \dfrac{(n+1)(n+2)}{2}$

C’est bien $P(n+1)$. ✓

Conclusion : Par récurrence, la propriété est vraie pour tout $n \geq 1$.

Le squelette à recopier

Notons P(n) : "..."

Initialisation :
   Pour n = n_0, ...
   Donc P(n_0) est vraie.

Hérédité :
   Soit n ≥ n_0 fixé.
   Supposons P(n) vraie (HR).
   Montrons P(n+1).
   [Calculs qui utilisent HR]
   Donc P(n+1) est vraie.

Conclusion :
   Par récurrence, P(n) est vraie pour tout n ≥ n_0.

Erreurs classiques

1. Oublier l’initialisation : sans base, la récurrence ne démarre pas.
2. Utiliser une propriété plus forte que $P(n)$ dans l’hérédité.
3. Ne pas indiquer où on utilise l’HR : le correcteur veut voir la ligne où tu appliques l’hypothèse.
4. Confondre « pour tout » et « pour un » : dans l’HR, $n$ est fixé, pas quantifié.

Cas fréquents au bac

• Somme d’entiers, de carrés, de puissances
• Inégalités (ex. $2^n \geq n + 1$ pour $n \geq 0$)
• Formule de récurrence : $u_n = \ldots$ pour une suite définie par récurrence
• Divisibilité (ex. $4^n - 1$ est divisible par 3)

?À toi de jouer

Dans une démo par récurrence, l'étape d'initialisation consiste à :

A.Vérifier que la propriété est vraie pour la plus petite valeurB.Supposer que la propriété est vraie pour un nC.Prouver que P(n+1) est vraieD.Conclure

Valider