L'effet domino : ce que prouve vraiment une récurrence
Objectif : Distinguer l'initialisation de l'hérédité et voir ce que chacune démontre séparément.
L’essentiel
Une démonstration par récurrence tient sur deux jambes. L'initialisation fait tomber le premier domino. L'hérédité garantit que tout domino qui tombe renverse le suivant.
À retenir
- Initialisation et hérédité sont deux preuves distinctes.
- L'hérédité seule est compatible avec une propriété fausse partout.
- On suppose la propriété à un rang quelconque, jamais pour tous.
⚠ Attention, piège
- Vérifie l'initialisation au bon rang. Beaucoup de propriétés ne deviennent vraies qu'à partir de 2 ou de 4 ; l'initialiser à 0 par habitude fait échouer une démonstration par ailleurs correcte.
Exemples
- Un alignement de dominos parfaitement réglé ne tombe pas tant que personne ne pousse le premier.
Le plan de la leçon
- Deux preuves, pas une
- L'hérédité seule ne démontre rien
- Ce qu'on suppose et ce qu'on prouve
Je me teste
Que démontre-t-on dans l'hérédité d'une récurrence ?
- Que la propriété est vraie pour tout entier naturel
- Que la propriété se transmet d'un rang au suivant
- Que la propriété est vraie au premier rang
Une propriété est héréditaire mais fausse au rang de départ. Que peut-on en dire ?
- Elle est vraie pour tous les rangs pairs
- Elle peut être fausse à tous les rangs
- Elle est vraie à partir du rang 1
À quoi sert la phrase « supposons la propriété vraie au rang n » ?
- À poser l'hypothèse de récurrence
- À conclure la démonstration
- À affirmer que la propriété est vraie
Le mot d’Oscar — Skelet, ta récurrence est héréditaire mais tu n'as pas initialisé.
Réponses : 1. B · 2. B · 3. A