Fiche de révision : Démonstration par récurrence

📋 Plan du Cours

1. Principe et domaine de récurrence
2. Modèle des dominos
3. Initialisation de la propriété
4. Hypothèse et hérédité
5. Calcul de l’hérédité
6. Conclusion de la démonstration

📖 1. Principe et domaine de récurrence

🔑 Notions clés & Définitions

• Démonstration par récurrence : Démonstration qui établit qu’une propriété définie sur les entiers est vraie à un premier rang, puis qu’elle est héréditaire d’un rang au suivant.

📝 Points essentiels

📌 L’initialisation vérifie la propriété au premier rang considéré, tandis que l’hérédité montre que sa véracité au rang k entraîne sa véracité au rang k+1.

💡 Astuce mémo

Initialisation → hérédité → conclusion

📖 2. Modèle des dominos

★ À maîtriser

• Le raisonnement des dominos suit deux étapes : faire tomber le premier domino, puis montrer que chaque domino tombé fait tomber le suivant.

Compléments

• Dans une file illimitée de dominos correctement espacés, la chute d’un domino entraîne celle du domino suivant.

💡 Astuce mémo

Un domino tombe → le suivant tombe → toute la file tombe

📖 3. Initialisation de la propriété

📝 Points essentiels

• L’initialisation consiste à vérifier directement que la propriété est vraie au premier entier considéré, noté n₀, qui peut être 0, 1, 2 ou un autre entier selon l’énoncé.

• Pour la propriété $2^n>n$ sur les entiers naturels non nuls, l’initialisation au rang 1 donne $2^1=2>1$.

📖 4. Hypothèse et hérédité

📝 Points essentiels

• 🔄 Pour démontrer l’hérédité:
  1. Choisir un entier k arbitraire
  2. Supposer la propriété vraie au rang k
  3. Démontrer la propriété vraie au rang k+1

📐 Formule — Pour la propriété $2^n>n$, l’hypothèse de récurrence au rang k est $2^k>k$, et l’objectif au rang suivant est $2^{k+1}>k+1$.

💡 Astuce mémo

Rang k supposé vrai, rang k+1 à démontrer

📖 5. Calcul de l’hérédité

📝 Points essentiels

📐 Formule — On décompose la puissance du rang suivant selon $2^{k+1}=2^k\times2$.

📐 Formule — En multipliant l’hypothèse $2^k>k$ par 2, on obtient $2^k\times2>k\times2$, donc $2^{k+1}>2k$.

📐 Formule — Comme k est un entier naturel non nul, $k\geq1$, donc $2k\geq k+1$ et finalement $2^{k+1}>k+1$.

💡 Astuce mémo

Décomposer → appliquer l’hypothèse → minorer

📖 6. Conclusion de la démonstration

📝 Points essentiels

• La conclusion s’obtient en combinant l’initialisation au rang 1 et l’hérédité, ce qui établit que la propriété est vraie pour tout entier naturel non nul.

📐 Formule — La démonstration conclut que, pour tout entier naturel non nul n, $2^n>n$.

📊 Tableaux de synthèse

Étapes de la récurrence