Raisonnement par récurrence

Suites (compléments) — Terminale Spécialité

Raisonnement par récurrence

1. Le principe de récurrence

Principe de récurrence : Soit P(n) une propriété dépendant d'un entier n. Pour démontrer que P(n) est vraie pour tout entier n ≥ n₀, il suffit de vérifier :

  1. Initialisation : P(n₀) est vraie.
  2. Hérédité : pour tout n ≥ n₀, si P(n) est vraie alors P(n+1) est vraie.

Si ces deux conditions sont remplies, alors P(n) est vraie pour tout entier n ≥ n₀.

Analogie des dominos : Le principe de récurrence fonctionne comme une file infinie de dominos :

  • L'initialisation fait tomber le premier domino.
  • L'hérédité garantit que chaque domino qui tombe entraîne la chute du suivant.
  • Donc tous les dominos tombent.

Attention : Les deux étapes sont indispensables :

  • Sans initialisation, l'hérédité seule ne prouve rien (les dominos ne démarrent jamais).
  • Sans hérédité, l'initialisation seule ne donne la propriété qu'en un seul point.

2. Rédaction rigoureuse d'une récurrence

Méthode : rédiger une démonstration par récurrence : Voici le plan de rédaction à suivre scrupuleusement :

  1. Énoncer la propriété : « Pour tout n ≥ n₀, posons P(n) : … »

  2. Initialisation : « Pour n = n₀ : … ». Calculer chaque membre et vérifier l'égalité (ou l'inégalité). Conclure : « P(n₀) est vraie. »

  3. Hérédité : « Soit n ≥ n₀ fixé. Supposons P(n) vraie (hypothèse de récurrence). Montrons que P(n+1) est vraie. » Puis effectuer le calcul en utilisant l'hypothèse de récurrence. Conclure : « P(n+1) est vraie. »

  4. Conclusion : « Par le principe de récurrence, P(n) est vraie pour tout n ≥ n₀. »

Erreurs classiques à éviter :

  1. Oublier d'énoncer P(n) clairement avant de commencer.
  2. Confondre « P(n) est vraie pour tout n » (ce qu'on veut prouver) avec « supposons P(n) vraie pour un n fixé » (hypothèse de récurrence).
  3. Ne pas utiliser l'hypothèse de récurrence dans l'étape d'hérédité.
  4. Vérifier P(n+1) directement sans partir de l'hypothèse P(n) — ce n'est pas une récurrence !
  5. Oublier la conclusion : il faut toujours terminer par la phrase de conclusion.

3. Récurrence simple : exemples variés

3.1 Récurrence et sommes

Exemple 1 : Somme des carrés : Montrer que pour tout n ≥ 1 : 1² + 2² + ⋯ + n² = (n(n+1)(2n+1))/6.

Posons P(n) : « 1² + 2² + ⋯ + n² = (n(n+1)(2n+1))/6 ».

Initialisation (n = 1) : la somme se réduit à 1² = 1, et (1 × 2 × 3)/6 = 1. P(1) est vraie. ✓

Hérédité : supposons P(n) vraie pour un n ≥ 1 fixé. Alors :

1² + 2² + ⋯ + (n+1)² = (1² + 2² + ⋯ + n²) + (n+1)²

= (n(n+1)(2n+1))/6 + (n+1)²

= (n(n+1)(2n+1) + 6(n+1)²)/6 = ((n+1)[n(2n+1) + 6(n+1)])/6

= ((n+1)(2n² + 7n + 6))/6 = ((n+1)(n+2)(2n+3))/6

C'est bien P(n+1). ✓

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

3.2 Récurrence et divisibilité

Exemple 2 : Divisibilité : Montrer que pour tout n ≥ 0 : 4ⁿ - 1 est divisible par 3.

Posons P(n) : « 3 | (4ⁿ - 1) » (c'est-à-dire 4ⁿ - 1 est un multiple de 3 ; la notation « | » vient de l'option Maths expertes).

Initialisation (n = 0) : 4⁰ - 1 = 0 = 3 × 0. P(0) est vraie. ✓

Hérédité : supposons P(n) vraie pour un n ≥ 0 fixé, c'est-à-dire 4ⁿ - 1 = 3k pour un certain k ∈ ℤ.

4ⁿ⁺¹ - 1 = 4 × 4ⁿ - 1 = 4(4ⁿ - 1) + 4 - 1 = 4 × 3k + 3 = 3(4k + 1)

Donc 4ⁿ⁺¹ - 1 est divisible par 3. P(n+1) est vraie. ✓

Conclusion : par récurrence, 3 | (4ⁿ - 1) pour tout n ≥ 0.

Méthode : récurrence et divisibilité : Pour montrer que aⁿ - bⁿ est divisible par (a - b), on écrit :

aⁿ⁺¹ - bⁿ⁺¹ = a · aⁿ - b · bⁿ = a(aⁿ - bⁿ) + (a - b) · bⁿ

On utilise l'hypothèse de récurrence sur aⁿ - bⁿ et on factorise.

3.3 Récurrence et inégalités

Exemple 3 : Inégalité : Montrer que pour tout n ≥ 5 : 2ⁿ > n².

Posons P(n) : « 2ⁿ > n² ».

Initialisation (n = 5) : 2⁵ = 32 et 5² = 25. On a bien 32 > 25. P(5) est vraie. ✓

Hérédité : supposons 2ⁿ > n² pour un n ≥ 5 fixé.

2ⁿ⁺¹ = 2 × 2ⁿ > 2n²

Il suffit de montrer que 2n² ≥ (n+1)² = n² + 2n + 1, c'est-à-dire n² - 2n - 1 ≥ 0.

Or n² - 2n - 1 = (n-1)² - 2 ≥ (5-1)² - 2 = 14 > 0 pour n ≥ 5.

Donc 2ⁿ⁺¹ > 2n² ≥ (n+1)². P(n+1) est vraie. ✓

Conclusion : par récurrence, 2ⁿ > n² pour tout n ≥ 5.

3.4 Récurrence et suites récurrentes

Exemple 4 : Suite récurrente : Soit (uₙ) définie par u₀ = 1 et uₙ₊₁ = 2uₙ + 3. Montrer que pour tout n ≥ 0 : uₙ = 4 × 2ⁿ - 3.

Posons P(n) : « uₙ = 4 × 2ⁿ - 3 ».

Initialisation (n = 0) : u₀ = 1 et 4 × 2⁰ - 3 = 4 - 3 = 1. P(0) est vraie. ✓

Hérédité : supposons uₙ = 4 × 2ⁿ - 3 pour un n ≥ 0 fixé.

uₙ₊₁ = 2uₙ + 3 = 2(4 × 2ⁿ - 3) + 3 = 8 × 2ⁿ - 6 + 3 = 4 × 2ⁿ⁺¹ - 3

P(n+1) est vraie. ✓

Conclusion : par récurrence, uₙ = 4 × 2ⁿ - 3 pour tout n ≥ 0.


4. Variantes et compléments

Récurrence à partir d'un rang quelconque : Le principe de récurrence fonctionne à partir de n'importe quel rang n₀ ∈ ℤ. Il suffit d'initialiser à n₀ et de montrer l'hérédité pour n ≥ n₀.

Il arrive souvent que la propriété ne soit vraie qu'à partir d'un certain rang : n ≥ 2, n ≥ 3, etc.

Méthode : trouver le bon rang d'initialisation :

  1. Vérifier pour quelles valeurs de n la propriété a un sens (par exemple, n! n'est défini que pour n ≥ 0).

  2. Tester les premières valeurs pour conjecturer le rang à partir duquel la propriété reste vraie (par exemple, 2ⁿ > n² est vraie pour n = 0 et 1, fausse pour n = 2, 3, 4 : on initialise à 5).

  3. Initialiser au bon rang n₀.

Exemple 6 : Inégalité avec factorielle : Montrer que pour tout n ≥ 4 : n! > 2ⁿ.

Posons P(n) : « n! > 2ⁿ ».

Initialisation (n = 4) : 4! = 24 et 2⁴ = 16. On a 24 > 16. P(4) est vraie. ✓

Hérédité : supposons n! > 2ⁿ pour un n ≥ 4 fixé.

(n+1)! = (n+1) × n! > (n+1) × 2ⁿ

Or n+1 ≥ 5 > 2, donc (n+1) × 2ⁿ > 2 × 2ⁿ = 2ⁿ⁺¹.

Ainsi (n+1)! > 2ⁿ⁺¹. P(n+1) est vraie. ✓

Conclusion : par récurrence, n! > 2ⁿ pour tout n ≥ 4.


5. Pour aller plus loin : la récurrence double

Récurrence double : Lorsque l'hérédité nécessite de connaître deux rangs consécutifs (par exemple pour une suite définie par uₙ₊₂ = f(uₙ, uₙ₊₁)), on utilise la récurrence double :

  1. Initialisation : vérifier P(n₀) et P(n₀ + 1).
  2. Hérédité : supposer P(n) et P(n+1) vraies pour un n ≥ n₀ fixé, puis montrer P(n+2).

Si ces conditions sont vérifiées, P(n) est vraie pour tout n ≥ n₀.

Notion pour aller plus loin.

Exemple 5 : Suite de Fibonacci : La suite de Fibonacci est définie par F₀ = 0, F₁ = 1 et Fₙ₊₂ = Fₙ₊₁ + Fₙ.

Montrer que pour tout n ≥ 0 : Fₙ ≤ 2ⁿ.

Posons P(n) : « Fₙ ≤ 2ⁿ ».

Initialisation :

  • P(0) : F₀ = 0 ≤ 1 = 2⁰ ✓
  • P(1) : F₁ = 1 ≤ 2 = 2¹ ✓

Hérédité : supposons P(n) et P(n+1) vraies pour un n ≥ 0 fixé, c'est-à-dire Fₙ ≤ 2ⁿ et Fₙ₊₁ ≤ 2ⁿ⁺¹.

Fₙ₊₂ = Fₙ₊₁ + Fₙ ≤ 2ⁿ⁺¹ + 2ⁿ = 2 × 2ⁿ + 2ⁿ = 3 × 2ⁿ ≤ 4 × 2ⁿ = 2ⁿ⁺²

Donc Fₙ₊₂ ≤ 2ⁿ⁺². P(n+2) est vraie. ✓

Conclusion : par récurrence double, Fₙ ≤ 2ⁿ pour tout n ≥ 0.

Quand utiliser la récurrence double ? : La récurrence double est commode lorsque :

  • La suite est définie par une relation de récurrence d'ordre 2 : uₙ₊₂ = f(uₙ, uₙ₊₁)
  • La propriété au rang n+2 dépend à la fois des rangs n et n+1
  • On a besoin de deux hypothèses pour conclure

Dans ce cas, il faut deux initialisations au lieu d'une seule.

On peut d'ailleurs toujours s'en passer : il suffit d'appliquer une récurrence simple à la propriété « P(n) et P(n+1) ».


À retenir

Résumé :

  1. Principe de récurrence : pour montrer P(n) pour tout n ≥ n₀, on vérifie P(n₀) (initialisation) et on montre P(n) ⇒ P(n+1) pour tout n ≥ n₀ (hérédité)

  2. Rédaction : toujours énoncer P(n), faire l'initialisation par calcul, écrire l'hypothèse de récurrence, montrer P(n+1), puis conclure

  3. Applications : la récurrence sert à prouver des formules de sommes, des propriétés de divisibilité, des inégalités, et des propriétés de suites récurrentes

  4. Récurrence double (pour aller plus loin) : quand l'hérédité nécessite deux rangs (P(n) et P(n+1) pour montrer P(n+2)), on initialise à deux rangs consécutifs

  5. Erreurs à éviter : ne pas oublier d'énoncer P(n), toujours utiliser l'hypothèse de récurrence dans l'hérédité, ne pas oublier la conclusion

  6. Rang d'initialisation : la récurrence peut démarrer à n'importe quel rang n₀ ; il faut choisir le bon rang selon la propriété