Comment prouver qu’une propriété est vraie pour tous les entiers naturels, alors qu’on ne peut pas les tester un par un ? Le raisonnement par récurrence fonctionne comme une chaîne de dominos : si le premier tombe et si chaque domino fait tomber le suivant, alors tous tombent.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Comprendre le principe de récurrence
- Rédiger une démonstration par récurrence complète et rigoureuse
- Démontrer une égalité, une inégalité ou une divisibilité par récurrence
- Utiliser la récurrence pour étudier une suite définie par u_{n+1} = f(u_{n})
1. Le principe de récurrence
Principe de récurrence : Soit P(n) une propriété dépendant d’un entier naturel n et n₀ un entier naturel. Si P(n₀) est vraie (initialisation) et si, pour tout entier n ≥ n₀, P(n) vraie implique P(n + 1) vraie (hérédité), alors P(n) est vraie pour tout entier n ≥ n₀.
- Initialisation : on vérifie que P(n₀) est vraie.
- Hérédité : on fixe un entier n ≥ n₀, on suppose P(n) vraie (c’est l’hypothèse de récurrence) et on démontre P(n + 1).
- Conclusion : par récurrence, P(n) est vraie pour tout n ≥ n₀.
2. Exemple : démontrer une égalité
Montrer que pour tout n ≥ 1 : 1 + 2 + … + n =
- Initialisation : pour n = 1, le membre de gauche vaut 1 et celui de droite vaut = 1. P(1) est vraie.
- Hérédité : soit n ≥ 1 tel que 1 + 2 + … + n = .
- Alors 1 + 2 + … + n + (n + 1) = + (n + 1) = (n + 1)( + 1) = .
- C’est exactement P(n + 1).
Par récurrence, l’égalité est vraie pour tout entier n ≥ 1.
3. Récurrence et suites
La récurrence est l’outil naturel pour les suites définies par une relation un+1 = f(un) : on peut démontrer qu’une suite est bornée, monotone, ou obtenir une formule explicite.
u₀ = 0 et un+1 = 0,5un + 1 : montrer que un ≤ 2 pour tout n
- Initialisation : u₀ = 0 ≤ 2.
- Hérédité : supposons un ≤ 2 pour un entier n fixé.
- Alors 0,5un ≤ 1, donc 0,5un + 1 ≤ 2, c’est-à-dire un+1 ≤ 2.
Pour tout entier naturel n, un ≤ 2 : la suite est majorée par 2.
4. Bien rédiger
- Énoncer clairement la propriété P(n) au début.
- Dans l’hérédité, écrire où l’on utilise l’hypothèse de récurrence.
- Partir de ce que l’on veut obtenir au rang n + 1 pour savoir quoi faire apparaître.
- Ne jamais supposer P(n) vraie « pour tout n » : c’est justement ce qu’on veut démontrer.
À retenir
- Une récurrence comporte trois étapes : initialisation, hérédité, conclusion.
- L’hérédité se démontre pour un entier n fixé quelconque.
- Sans initialisation, une propriété héréditaire peut être fausse.
- La récurrence permet de prouver qu’une suite est bornée, monotone, ou d’en trouver le terme général.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.