Revision sheet: Introduction à la récurrence et ses applications

📋 Plan du Cours

1. Raisonnement par récurrence
2. Illustration des dominos
3. Principe de récurrence
4. Somme des entiers naturels
5. Suite définie par récurrence
6. Encadrement et croissance de u_n

📖 1. Raisonnement par récurrence

🔑 Notions clés & Définitions

• Dominos : Métaphore où la chute d’un domino entraîne la chute du suivant pour garantir un résultat pour toute une chaîne.
• Propriété P(n) : Notation d’une propriété qui dépend d’un entier naturel n et qu’on veut montrer vraie à partir d’un certain rang.
• Vérification initiale : Étape où l’on démontre que P(n0) est vraie pour amorcer la chaîne de raisonnement.

📝 Points essentiels

• Pour conclure que P(n) est vraie pour tout n ≥ n0, on combine un point de départ et une preuve de passage de k vers k+1.
• La logique de l’approche repose sur le fait que la chute du kème entraîne celle du (k+1)ème.
• Le cours demande de viser une propriété P(n) formulée en fonction de n avant de faire l’amorçage puis la hérédité.

💡 Astuce mémo

Dominos = départ (1er tombe) puis relais (k tombe ⇒ k+1 tombe).

📖 2. Illustration des dominos

🔑 Notions clés & Définitions

• Chute du premier domino : Premier maillon : prouver que le domino de départ tombe afin que la réaction en chaîne puisse démarrer.
• Chute du kème domino : Moment où l’on suppose qu’un domino quelconque tombe pour pouvoir en déduire la suite.
• Chute du (k+1)ème domino : Conséquence : à partir de la chute du kème, on démontre que le domino suivant tombe aussi.

📝 Points essentiels

• L’illustration met en scène trois idées : un premier domino qui tombe, une hypothèse à un rang k, puis un domino suivant obtenu grâce à cette hypothèse.
• Le rôle de la variable k est d’être quelconque à partir d’un rang de départ (k ≥ n0) avant d’enchaîner jusqu’à k+1.
• L’illustration sert à comprendre l’enchaînement logique : l’hypothèse au rang k suffit pour conclure au rang k+1.

💡 Astuce mémo

Si k tombe, alors k+1 tombe : c’est le “mécanisme de transfert” des dominos.

📖 3. Principe de récurrence

🔑 Notions clés & Définitions

• Axiome de récurrence : Principe admis qui formalise la preuve par étapes : départ, hypothèse de récurrence, puis hérédité.
• Hypothèse de récurrence : Supposition de travail : on suppose P(k) vraie pour un entier k ≥ n0 avant de prouver P(k+1).
• Hérédité : Étape où l’on déduit P(k+1) à partir de l’hypothèse que P(k) est vraie.

📝 Points essentiels

• On veut montrer que pour tout n ≥ n0, P(n) est vraie en vérifiant successivement P(n0), puis l’implication P(k) ⇒ P(k+1), puis la conclusion générale.
• L’axiome formule k comme un entier naturel quelconque vérifiant k ≥ n0, pour éviter de dépendre d’une valeur particulière.
• Le raisonnement suit exactement trois blocs : vérification initiale, hypothèse de récurrence, puis démonstration de P(k+1).

💡 Astuce mémo

Schéma : Initiale → Hypothèse → Hérédité ⇒ Tous les n.

📖 4. Somme des entiers naturels

🔑 Notions clés & Définitions

• Somme 1 + 2 + … + n : Expression de somme des entiers consécutifs à partir de 1 jusqu’à n.
• Propriété P(n) de somme : Formulation de l’objectif : écrire l’égalité reliant 1 + 2 + … + n à une expression en n.
• Formule de la somme : Expression de référence : 1 + 2 + … + n se met sous la forme n(n+1)/2 pour n ≥ 1.

📝 Points essentiels

• Pour n ≥ 1, on choisit P(n) : 1 + 2 + … + n = n(n+1)/2.
• On vérifie P(1) : 1 = 1×(1+1)/2, puis on suppose la formule vraie pour k.
• On prouve P(k+1) en partant de 1 + 2 + … + k + (k+1) et en transformant pour obtenir (k+1)(k+2)/2.

💡 Astuce mémo

Somme = n(n+1)/2 : penser “produit des deux voisins”.

📖 5. Suite définie par récurrence

🔑 Notions clés & Définitions

• Suite (t_n) : Suite définie par une relation de récurrence qui exprime t_{n+1} à partir de t_n.
• Suite (u_n) : Suite définie avec u_{n+1} calculée à partir de u_n via une racine carrée.
• Récurrence t_{n+1}=3t_n−2 : Règle de mise à jour permettant de calculer chaque terme suivant à partir du précédent.
• Récurrence u_{n+1}=√(u_n+5) : Règle reliant un terme à son successeur par une racine carrée.

📝 Points essentiels

• Dans l’exemple 1, t0 = 0 et t_{n+1} = 3t_n − 2, puis on démontre par récurrence que t_n = 1 − 3^n pour tout n.
• Dans l’exemple 2, u0 = 0 et u_{n+1} = √(u_n+5), puis on démontre d’abord 0 < u_n < 3 pour n ≥ 1.
• Pour montrer la croissance, on utilise l’implication : u_k < u_{k+1} ⇒ u_{k+1} < u_{k+2} obtenue en appliquant la racine carrée et en ajoutant 5.

💡 Astuce mémo

Règle → calcul : t_{n+1} dépend de t_n, u_{n+1} dépend de u_n via √(u_n+5).

📖 6. Encadrement et croissance de u_n

🔑 Notions clés & Définitions

• Encadrement 0 < u_n < 3 : Intervalle de valeurs où l’on prouve que u_n se situe pour tout n à partir d’un rang fixé.
• Suite croissante : Propriété où chaque terme est strictement inférieur au suivant : u_n < u_{n+1} pour tout n considéré.
• Racine carrée croissante : Propriété de monotonicité : la fonction √x conserve l’ordre sur [0, +∞[.

📝 Points essentiels

• Pour l’encadrement, on pose P(n) : 0 < u_n < 3 et on vérifie P(1) avec u1 = √5.
• Pour l’hérédité de l’encadrement, de 0 < u_k < 3 on déduit 5 < u_k+5 < 8 puis √5 < √(u_k+5) < √8.
• Pour la croissance, on pose P(n) : u_n < u_{n+1}, puis on utilise la croissance de √· sur [0,+∞[ pour conclure que u_{k+1} < u_{k+2}.

💡 Astuce mémo

Encadrement : 0<u_k<3 ⇒ 5<u_k+5<8 ⇒ √5<u_{k+1}<√8<3.

⚠️ Pièges & confusions fréquents

1. Confondre l’hypothèse de récurrence (supposer P(k) vraie) avec la conclusion à démontrer (prouver P(k+1) vraie).
2. Oublier la vérification initiale (P(n0)) : sans départ, la “chaîne des dominos” ne démarre pas.
3. Raisonner pour une valeur particulière de k au lieu de k quelconque vérifiant k ≥ n0.
4. Mauvaise application de la croissance de la racine carrée : elle n’est valable que sur [0, +∞[ et nécessite donc des expressions positives.
5. S’emmêler entre u_{n+1} = √(u_n+5) et u_{n+1} = √u_n + 5 : ce n’est pas la même écriture.
6. Démontrer la croissance sans montrer le lien entre l’inégalité u_k < u_{k+1} et celle après application de √· (et donc avec l’ajout 5).

✅ Checklist Examen

1. Savoir formuler clairement une propriété P(n) dépendant d’un entier naturel n et un rang de départ n0.
2. Vérifier P(n0) pour amorcer la récurrence.
3. Présenter une hypothèse de récurrence du type “supposons P(k) vraie pour un k ≥ n0”.
4. Démontrer l’hérédité : en partant de P(k), conclure que P(k+1) est vraie.
5. Conclure que P(n) est vraie pour tout entier n ≥ n0 à partir des trois étapes.
6. Reproduire la démonstration par récurrence de 1 + 2 + … + n = n(n+1)/2 pour n ≥ 1.
7. Pour l’exemple t_n, partir de t0 = 0 et t_{n+1}=3t_n−2, puis appliquer une récurrence pour obtenir t_n = 1−3^n.
8. Pour l’exemple u_n, établir par récurrence que pour tout n ≥ 1, 0 < u_n < 3.
9. Montrer que la suite (u_n) est croissante en prouvant u_n < u_{n+1} pour tous les n requis.
10. Savoir utiliser la croissance de la fonction racine carrée sur [0,+∞[ pour transformer une inégalité sur les u_n en une inégalité sur les u_{n+1}.