Le raisonnement par récurrence : l'échelle aux barreaux infinis
Objectif : Ne plus se tromper sur : Le raisonnement par récurrence.
L’essentiel
Comment prouver qu'une propriété est vraie pour TOUS les entiers — une infinité de cas ? Le RAISONNEMENT PAR RÉCURRENCE le fait en deux vérifications finies, et son image officielle est l'ÉCHELLE : si je peux monter sur le PREMIER barreau, et si DEPUIS N'IMPORTE QUEL barreau je sais passer au suivant, alors je peux atteindre tous les barreaux.
À retenir
- Trois actes : INITIALISATION (P(0), une ligne, obligatoire), HÉRÉDITÉ (P(n) pour UN n ⟹ P(n+1)), CONCLUSION (la phrase rituelle).
- L'hérédité propage le vrai COMME le faux : sans initialisation, rien n'est prouvé (« 3 divise 4ⁿ+1 » : le contre-exemple de poche).
- L'hypothèse porte sur UN entier quelconque — « pour tout n » dans l'hérédité est le serpent qui suppose la conclusion.
- L'hypothèse doit SERVIR : l'injection de P(n) dans la relation est le geste attendu.
- Suite démarrant à n₀ : initialiser au premier VRAI barreau, conclure « pour tout n ≥ n₀ ».
Le tableau à connaître
| L'Acte | Le Geste | L'Exemple (uₙ ≤ 3) | Le Détail |
|---|---|---|---|
| Nommer P(n) | La propriété, dépendant de n, énoncée SEULE | P(n) : « uₙ ≤ 3 » | Sans le « pour tout n » : c'est la conclusion, pas P(n) |
| L'initialisation | Vérifier P(0) — ou P(n₀) si la suite démarre plus loin | u₀ = 1 ≤ 3 ✓ | Une ligne, mais OBLIGATOIRE |
| L'hérédité | Supposer P(n) pour UN n, démontrer P(n+1) | uₙ ≤ 3 ⟹ √(uₙ+6) ≤ 3 | Le cœur du travail — l'hypothèse SERT |
| La conclusion | Invoquer le principe, les deux actes cités | « Initialisée et héréditaire : vraie pour tout n » | La phrase rituelle, jamais omise |
| L'usage roi | Suites récurrentes : bornes, sens, formules | uₙ₊₁ = f(uₙ) : la borne se propage | La récurrence parle aux récurrences |
| L'image | L'échelle aux barreaux infinis | Premier barreau + passage : tout est atteint | Les dominos alignés, version verticale |
⚠ Attention, piège
- La faute d'échelle : l'hérédité SANS initialisation — le passage de barreau en barreau ne sert à rien si l'on n'est monté sur AUCUN : la propriété « 3 divise 4ⁿ + 1 » est parfaitement héréditaire… et fausse pour tout n (aucun barreau de départ n'existe) — le…
Exemples
- L'hérédité type, sur une formule explicite : montrer que uₙ = 2ⁿ − 1 pour la suite u₀ = 0, uₙ₊₁ = 2uₙ + 1 — hypothèse : uₙ = 2ⁿ − 1 pour un n ; alors uₙ₊₁ = 2(2ⁿ − 1) +…
- La rédaction complète, gabarit du bac : « Notons P(n) la propriété : uₙ ≤ 3. — Initialisation : u₀ = 1 ≤ 3, P(0) est vraie. — Hérédité : soit n un entier tel que P(n)…
Mots-clés
P(n)2ⁿ⁺¹ − 1
Le plan de la leçon
- Démontrer pour Tous les Entiers d'un Coup
- Le Protocole en Trois Actes
- L'Hérédité au Travail
- Le Piège de l'Hérédité Sans Initialisation
Je me teste
Dans l'hérédité, que suppose-t-on exactement ?
- P(n+1) vraie
- P(n) vraie pour UN entier n quelconque — et on démontre P(n+1)
- P(n) vraie pour TOUS les entiers
« 3 divise 4ⁿ + 1 » est héréditaire (si 3 divise 4ⁿ + 1, alors 3 divise 4ⁿ⁺¹ + 1... se vérifie). La propriété est-elle vraie ?
- Oui, à partir d'un certain rang
- Non, pour aucun n
- Oui
Le mot d’Oscar — Dossier de démonstration : la récurrence. Skelet, le conseil exige la preuve que la dette du domaine, régie par uₙ₊₁ = √(uₙ + 6) depuis u₀ = 1, ne dépassera JAMAIS 3 talents — pour tous les siècles à venir.
Réponses : 1. B · 2. B