Lernzettel: Le raisonnement par récurrence

📋 Plan du Cours

1. Axiome et principe de récurrence
2. Mise en œuvre de la démonstration
3. Application à l'étude d'une suite

📖 1. Axiome et principe de récurrence

🔑 Notions clés & Définitions

• Raisonnement par récurrence : Consiste à prouver un cas de base (généralement n=1), puis à prouver que si l'affirmation est vraie pour un entier k, elle est aussi vraie pour l'entier suivant k+1.

📝 Points essentiels

★ À maîtriser

• Soit P(n) une propriété dépendant d'un entier naturel n ; si P(n) est vraie pour un entier initial (initialisation) et si pour tout entier naturel l'hérédité est vérifiée, alors on peut affirmer que P(n) est vraie pour tout entier supérieur ou égal à cet entier initial.

Compléments

• La propriété P(n) peut être de différentes natures : une égalité, une inégalité, ou une phrase exprimant par exemple qu'une expression est un entier naturel.
• On peut illustrer le raisonnement par récurrence par la programmation d'un robot qui doit monter des escaliers : si le robot est mis sur une marche et sait monter d'une marche à la suivante, alors il saura monter toutes les marches à partir de cette marche.

📖 2. Mise en œuvre de la démonstration

📝 Points essentiels

★ À maîtriser

• L'initialisation est la démonstration que la propriété P(n) est vraie au rang initial choisi.
• L'hérédité est une implication à montrer : on considère un entier k et on suppose que P(k) est vraie (hypothèse de récurrence), puis on démontre que P(k+1) est alors vraie en utilisant cette hypothèse.
• On aboutit à la conclusion que P(n) est vraie pour tout entier naturel n supérieur ou égal au rang initial après avoir prouvé l'initialisation et l'hérédité.

Compléments

• L'hypothèse de récurrence est le fait de supposer que la propriété P(k) est vraie au rang k afin d'en déduire qu'elle est vraie au rang k+1.

📖 3. Application à l'étude d'une suite

📝 Points essentiels

★ À maîtriser

• Pour la suite définie par u₀=0 et u_{n+1}=√(u_n+2), on démontre par récurrence que 0 ≤ u_n ≤ 2.
• Pour l'hérédité, on suppose 0 ≤ u_k ≤ 2 ; comme la fonction racine carrée est croissante, on en déduit 0 ≤ √(u_k+2) ≤ 2, soit 0 ≤ u_{k+1} ≤ 2, donc P(k+1) est vraie.

Compléments

• Pour l'initialisation, u₀=0 donc 0 ≤ u₀ ≤ 2 et P(0) est vraie.

⚠️ Pièges & confusions fréquents

1. L'axiome de récurrence nécessite de démontrer l'initialisation ET l'hérédité ; l'un sans l'autre ne suffit pas à conclure.
2. L'hérédité ne consiste pas à prouver P(k+1) à partir de rien, mais à utiliser explicitement l'hypothèse de récurrence P(k) pour établir P(k+1).

✅ Checklist Examen

1. Raisonnement par récurrence
2. Soit P(n) une propriété dépendant d'un entier naturel n ; si P(n) est vraie pour un entier initial (initialisation) et si pour tout entier naturel
3. L'initialisation est la démonstration que la propriété P(n) est vraie au rang initial choisi.
4. Pour la suite définie par u₀=0 et u_{n+1}=√(u_n+2), on démontre par récurrence que 0 ≤ u_n ≤ 2.
5. L'hérédité est une implication à montrer : on considère un entier k et on suppose que P(k) est vraie (hypothèse de récurrence)
6. Pour l'hérédité, on suppose 0 ≤ u_k ≤ 2 ; comme la fonction racine carrée est croissante, on en déduit 0 ≤ √(u_k+2) ≤ 2, soit 0 ≤ u_{k+1} ≤ 2
7. On aboutit à la conclusion que P(n) est vraie pour tout entier naturel n supérieur ou égal au rang initial après avoir prouvé l'initialisation