Le principe de récurrence
Pour démontrer qu'une propriété P(n) est vraie pour tout entier n à partir d'un rang n₀, on procède en deux étapes.
- Initialisation : on vérifie que P(n₀) est vraie.
- Hérédité : on suppose P(n) vraie pour un entier n ≥ n₀ (hypothèse de récurrence), et on démontre que P(n + 1) est vraie.
- Conclusion : P(n) est vraie pour tout entier n ≥ n₀.
- L'hérédité doit utiliser l'hypothèse de récurrence : sans elle, on ne démontre rien.
Exercice 1 Une somme
Démontrer par récurrence que, pour tout entier n ≥ 1, 1 + 2 + 3 + … + n = n(n + 1)/2.
Un indice
Dans l'hérédité, ajoutez n + 1 des deux côtés de l'égalité supposée vraie au rang n.
Voir la correction
Initialisation : pour n = 1, le membre de gauche vaut 1 et le membre de droite vaut 1 × 2/2 = 1. La propriété est vraie.
Hérédité : supposons 1 + 2 + … + n = n(n + 1)/2 pour un entier n ≥ 1. Alors 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n/2 + 1) = (n + 1)(n + 2)/2.
C'est la propriété au rang n + 1. Par récurrence, elle est vraie pour tout entier n ≥ 1.
Exercice 2 Une inégalité
Démontrer que, pour tout entier n ≥ 0, 2ⁿ ≥ n + 1.
Un indice
Pour l'hérédité, multipliez l'inégalité de l'hypothèse de récurrence par 2, puis comparez avec n + 2.
Voir la correction
Initialisation : pour n = 0, 2⁰ = 1 et n + 1 = 1, donc 1 ≥ 1 est vrai.
Hérédité : supposons 2ⁿ ≥ n + 1 pour un entier n ≥ 0. Alors 2ⁿ⁺¹ = 2 × 2ⁿ ≥ 2(n + 1) = 2n + 2.
Or 2n + 2 ≥ n + 2 puisque n ≥ 0. Donc 2ⁿ⁺¹ ≥ (n + 1) + 1 : la propriété est vraie au rang n + 1.
Par récurrence, 2ⁿ ≥ n + 1 pour tout entier n ≥ 0.
Exercice 3 Une divisibilité
Démontrer que, pour tout entier n ≥ 0, 4ⁿ − 1 est divisible par 3.
Un indice
Écrivez 4ⁿ⁺¹ − 1 = 4(4ⁿ − 1) + 3 pour faire apparaître l'hypothèse de récurrence.
Voir la correction
Initialisation : pour n = 0, 4⁰ − 1 = 0, qui est divisible par 3.
Hérédité : supposons que 4ⁿ − 1 soit divisible par 3, c'est-à-dire 4ⁿ − 1 = 3k avec k entier. Alors 4ⁿ⁺¹ − 1 = 4 × 4ⁿ − 1 = 4(4ⁿ − 1) + 4 − 1 = 4 × 3k + 3 = 3(4k + 1).
Donc 4ⁿ⁺¹ − 1 est un multiple de 3. Par récurrence, 4ⁿ − 1 est divisible par 3 pour tout n ≥ 0.
Exercice 4 Une formule pour une suite
La suite (uₙ) est définie par u₀ = 1 et uₙ₊₁ = 2uₙ + 1. Démontrer que, pour tout n, uₙ = 2ⁿ⁺¹ − 1.
Un indice
Dans l'hérédité, remplacez uₙ par 2ⁿ⁺¹ − 1 dans la formule de récurrence.
Voir la correction
Initialisation : u₀ = 1 et 2⁰⁺¹ − 1 = 2 − 1 = 1. La formule est vraie au rang 0.
Hérédité : supposons uₙ = 2ⁿ⁺¹ − 1. Alors uₙ₊₁ = 2uₙ + 1 = 2(2ⁿ⁺¹ − 1) + 1 = 2ⁿ⁺² − 2 + 1 = 2ⁿ⁺² − 1.
C'est la formule au rang n + 1. Contrôle : u₁ = 3 = 2² − 1 et u₂ = 7 = 2³ − 1. Par récurrence, uₙ = 2ⁿ⁺¹ − 1 pour tout n.
Les erreurs à éviter
- Oublier l'initialisation : sans elle, la chaîne d'implications ne démarre jamais.
- Démontrer l'hérédité sans utiliser l'hypothèse de récurrence.
- Supposer la propriété vraie pour tout n dans l'hérédité, alors qu'on la suppose pour un seul entier fixé.
- Oublier la conclusion écrite : « par récurrence, la propriété est vraie pour tout entier n ≥ n₀ ».
Questions fréquentes
Pourquoi la récurrence fonctionne-t-elle ?
L'initialisation donne le premier rang, l'hérédité transmet la propriété de chaque rang au suivant : elle atteint donc tous les entiers, comme des dominos qui tombent.
Peut-on commencer à un rang autre que 0 ou 1 ?
Oui, à n'importe quel rang n₀ : l'initialisation se fait alors à ce rang, et la conclusion vaut pour tout n ≥ n₀.
Comment bien rédiger l'hérédité ?
En écrivant l'hypothèse de récurrence, en partant du membre de gauche au rang n + 1, puis en la faisant apparaître pour arriver au résultat attendu.