Raisonnement par récurrence : exercices corrigés

La récurrence prouve qu'une propriété est vraie pour tous les entiers, en démontrant deux choses : elle commence, et elle se transmet. Quatre exercices pour rédiger proprement ce raisonnement dans quatre situations différentes.

Mathématiques · Terminale ·

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.

À revoir avant

Pour continuer

Prêt à faire le point ?

Un premier rendez-vous de 30 minutes, offert, pour faire connaissance avec l'élève et ses parents.

ou appeler le +33 7 45 30 60 01