Fiche de cours Logimaths
Raisonnement par récurrence : le cours expliqué pas à pas
Effet dominos : initialisation + hérédité
💡 Avant de commencer Version expliquée pas à pas. L'idée clé : la récurrence, c'est l'effet dominos : si le premier tombe et que chaque domino fait tomber le suivant, tous tombent.
Étape 1 : Le principe des dominos
Pour démontrer qu'une propriété est vraie pour tous les entiers, deux choses suffisent : montrer qu'elle est vraie au départ, et que si elle est vraie à un rang, elle l'est au suivant. Comme des dominos alignés.
Étape 2 : L'initialisation
Étape 1 de la preuve On vérifie que la propriété est vraie au premier rang (souvent n = 0 ou n = 1) : c'est « faire tomber le premier domino ».
Étape 3 : L'hérédité
Étape 2 de la preuve On suppose la propriété vraie à un rang n (hypothèse de récurrence), et on démontre qu'elle est alors vraie au rang n + 1 : « chaque domino fait tomber le suivant ».
Étape 4 : La rédaction type
Plan
1) Énoncer la propriété P(n).
2) Initialisation : vérifier que P(n) est vraie au premier rang.
3) Hérédité : supposer P(k) vraie pour un entier k fixé,
puis prouver que P(k+1) est vraie à son tour.
4) Conclusion : P(n) est vraie pour tout n.
2) Initialisation : vérifier que P(n) est vraie au premier rang.
3) Hérédité : supposer P(k) vraie pour un entier k fixé,
puis prouver que P(k+1) est vraie à son tour.
4) Conclusion : P(n) est vraie pour tout n.
👆 À toi de jouer Vérifie l'initialisation de 1 + 2 + … + n = n(n+1)2 au rang 1.
Voir la réponse
À gauche : 1. À droite : 1×2/2 = 1. Égalité vraie : initialisation OK.🎯 Mémo
L'essentiel Récurrence = dominos. Deux étapes : initialisation (le 1er tombe) + hérédité (chacun fait tomber le suivant). Rédaction en 4 temps.