Notions de logique · Leçon 5
Raisonnement par récurrence
Une longue file de dominos. On sait que :
- (1) le premier domino tombe ;
- (2) chaque domino qui tombe fait tomber le suivant.
Que peut-on conclure ?
Principe de récurrence
Soit une propriété qui dépend d'un entier , et . Si :
- Initialisation : est vraie,
- Hérédité : pour tout , ,
alors est vraie pour tout entier .
L'escalier
Tu sais monter sur la première marche. Et depuis n'importe quelle marche, tu sais monter sur la suivante. Alors tu peux monter tout l'escalier.
Monte l'escalier
Choisis les deux conditions, puis monte.
Rédaction type
Initialisation : pour , … donc est vraie.
Hérédité : soit . Supposons que est vraie (hypothèse de récurrence) et montrons que est vraie. …
Conclusion : d'après le principe de récurrence, pour tout , est vraie.
L'hypothèse de récurrence
Dans l'hérédité, on fixe un entier et on suppose pour cet entier.
Écrire « supposons que pour tout , est vraie » revient à supposer ce qu'on veut démontrer !
Observer avant de démontrer
Voici les valeurs de .
La dernière colonne donne le reste de la division de par le diviseur. Reste veut dire « divisible ».
Essaie d'autres diviseurs : , , …
| reste ÷ 5 | ||
|---|---|---|
| 0 | 0 | 0 |
| 1 | 5 | 0 |
| 2 | 45 | 0 |
| 3 | 335 | 0 |
| 4 | 2385 | 0 |
| 5 | 16775 | 0 |
| 6 | 117585 | 0 |
| 7 | 823415 | 0 |
| 8 | 5764545 | 0 |
Avec , le reste vaut sur toutes les lignes. On devine que divise pour tout .
Un tableau ne prouve rien. La méthode suivante le démontre.
L'astuce de l'hérédité (divisibilité)
On écrit le terme de rang en fonction de celui de rang , pour faire apparaître l'hypothèse de récurrence :
Si divise , les deux termes sont des multiples de .
L'hérédité seule ne suffit pas
: « divise » est héréditaire : si , alors .
Pourtant est fausse pour tout : , … Sans initialisation, aucune conclusion !
Deviner une formule
Compare les deux colonnes, ligne par ligne.
- Colonne 1 : la somme des cubes, .
- Colonne 2 : le carré de la somme, .
| 1 | 1 | 1 |
| 2 | 9 | 9 |
| 3 | 36 | 36 |
| 4 | 100 | 100 |
| 5 | 225 | 225 |
| 6 | 441 | 441 |
Les deux colonnes sont égales sur toutes les lignes. On devine la formule :
Six lignes ne sont pas « pour tout ». Pour le démontrer, on utilise la récurrence.