Raisonnement par récurrence
Méthode de preuve pour montrer qu’une propriété est vraie pour tout entier à partir d’un rang donné.
1
Principe
Schéma général
Repères
- Une propriété dépend de l’entier
n. - But : montrer P(n) pour tout n ≥ n0.
2
Initialisation
Départ de la preuve
- 1
Écrire la propriété P(n).
- 2
Remplacer n par le rang initial.
- 3
Effectuer le calcul complètement.
Pièges
Oublier le premier cas rend la preuve incomplète. Choisis toujours le rang de départ avant de calculer.
3
Hérédité
Transmission
On suppose
- P(n) vraie.
- n reste arbitraire.
- Aucune valeur particulière.
On démontre
- P(n+1) vraie.
- On utilise l’hypothèse autorisée.
- On obtient le résultat attendu.
Formulation
- Supposer P(n) vraie.
- Travailler sous l’hypothèse de récurrence.
4
Conclusion
Règle de fin
L’initialisation et l’hérédité permettent d’affirmer la propriété pour tout entier du domaine.
Ce qu’il faut écrire
- Rappeler les deux vérifications.
- Conclure clairement pour tout n du domaine.
5
Rédaction rigoureuse
Choix de la propriété
| À faire | Pourquoi |
|---|---|
| Formuler P(n) précisément. | La propriété doit être démontrable. |
| Choisir un rang de départ clair. | La preuve commence au bon endroit. |
| Adapter P(n) au calcul. | L’hérédité doit rester manipulable. |
Mini-défi
- Identifier l’étape qui vérifie le premier rang.
- Nommer l’étape qui utilise l’hypothèse de récurrence.
À retenir
- Initialisation, hérédité, conclusion.
- La propriété doit être bien choisie.
- La rédaction doit être claire et justifiée.
- Sans hypothèse de récurrence, pas de preuve par récurrence.