Analyse · Tle
Le raisonnement par récurrence
Une propriété vraie au départ, et qui se transmet d'un rang au suivant : voilà tout ce qu'il faut pour qu'elle soit vraie partout.
La démonstration en vidéo
Le vocabulaire à connaître
- initialisation
- La vérification que la propriété P(n) est vraie au premier rang étudié, souvent n = 0 ou n = 1.
- hérédité
- La démonstration que, SI P(n) est vraie à un rang n quelconque, ALORS elle reste vraie au rang n + 1 — une implication, pas une affirmation.
- hypothèse de récurrence
- La supposition « P(n) est vraie », posée au début de l'hérédité, dont on se sert pour démontrer P(n + 1).
Ce qu'on sait
- Une démonstration par récurrence comporte toujours trois étapes, dans cet ordre : initialisation : La vérification que la propriété P(n) est vraie au premier rang étudié, souvent n = 0 ou n = 1., hérédité : La démonstration que, SI P(n) est vraie à un rang n quelconque, ALORS elle reste vraie au rang n + 1 — une implication, pas une affirmation., conclusion.
- L'hérédité seule ne prouve jamais rien : sans initialisation, on ne sait pas où la propriété commence à être vraie, si elle l'est un jour.
- La récurrence sert à établir des propriétés d'une suite : une majoration uₙ ≤ M, une minoration uₙ ≥ m, un sens de variation, ou une inégalité plus générale.
La méthode, étape par étape
1.J'énonce clairement la propriété P(n) que je veux démontrer pour tout n à partir d'un rang n₀.
2.Initialisation : je vérifie que P(n₀) est vraie, en général par un calcul direct.
3.Hérédité : je suppose P(n) vraie à un rang n quelconque (l'hypothèse de récurrence : La supposition « P(n) est vraie », posée au début de l'hérédité, dont on se sert pour démontrer P(n + 1).), et j'en déduis, par le calcul, que P(n + 1) est vraie aussi.
4.Conclusion : par le principe de récurrence, P(n) est vraie pour tout entier n supérieur ou égal à n₀.
Initialisation vraie + hérédité vraie ⟹ P(n) est vraie pour tout entier n à partir du rang initial.
C.Q.F.D.
L'exemple au propre
1.Montrons que uₙ ≤ 6 pour tout n, sachant u₀ = 0 et uₙ₊₁ = 0,5 × uₙ + 3.
2.Initialisation : u₀ = 0 ≤ 6, vrai.
3.Hérédité : je suppose uₙ ≤ 6. Alors uₙ₊₁ = 0,5 × uₙ + 3 ≤ 0,5 × 6 + 3 = 6.
4.Par récurrence, uₙ ≤ 6 pour tout entier n.