AdmirEdu · Fiche de révision
Nom : ………………………………
Le raisonnement par récurrence · Tle
Propriété — Principe de récurrence
Soit P(n) une propriété dépendant d'un entier n et n_0 un entier. Si P(n_0) est vraie (initialisation) et si, pour tout entier n≥ n_0, P(n) vraie entraîne P(n+1) vraie (hérédité), alors P(n) est vraie pour tout n≥ n_0 (conclusion).
Méthode — Rédiger une récurrence
- Énoncer clairement P(n).
- Initialisation : vérifier P(n_0) par le calcul.
- Hérédité : « Soit n≥ n_0 tel que P(n) est vraie » (hypothèse de récurrence, HR). Montrer P(n+1) en utilisant l'HR.
- Conclusion : « Par récurrence, P(n) est vraie pour tout n≥ n_0. »
Méthode — Pour une suite uₙ₊₁ = f(uₙ)
- Encadrement a≤ u_n≤ b : on applique des opérations ou une fonction croissante à l'encadrement.
- Sens de variation : on démontre u_n≤ u_n+1 par récurrence, en appliquant f croissante : f(u_n)≤ f(u_n+1), c'est-à-dire u_n+1≤ u_n+2.
Exemple type — L'inégalité de Bernoulli
Soit a>0. Démontrer que pour tout entier n0, (1+a)^n1+na.
- P(n) : (1+a)^n1+na. Initialisation : (1+a)^0=11+0 ✓.
- Hérédité : soit n0 tel que (1+a)^n1+na. Comme 1+a>0, on multiplie : .
- car na^20. Donc P(n+1) est vraie.
Par récurrence, (1+a)^n1+na pour tout n0 — d'où l'on déduira que q^n+∞ si q>1.
Rédaction type
Démontrer une formule de somme : 1^2+2^2+·s+n^2
Pour tout entier n1, on note P(n) : « ».
Initialisation. Pour n=1 : 1^2=1 et (1×2×3)/(6)=1, donc P(1) est vraie.
Hérédité. Supposons que P(n) est vraie pour un entier n1 : .
Alors
=((n+1) [n(2n+1)+6(n+1) ])/(6)
=((n+1)(2n^2+7n+6))/(6)
Or (n+2)(2n+3)=2n^2+7n+6, donc la somme vaut ((n+1)(n+2)(2n+3))/(6) : P(n+1) est vraie.
Conclusion. P(1) est vraie et la propriété est héréditaire, donc par récurrence P(n) est vraie pour tout entier n1.
Encadrer une suite définie par u_n+1=f(u_n)
Soit (u_n) définie par u_0=2 et u_n+1=12u_n+3. Pour tout n0, on note P(n) : « 0≤ u_n6 ».
Initialisation. u_0=2 et 026, donc P(0) est vraie.
Hérédité. Supposons que P(n) est vraie pour un entier n0 : 0≤ u_n6.
En multipliant par 12>0 : .
En ajoutant 3 : , soit . Donc : P(n+1) est vraie.
Conclusion. Par récurrence, 0≤ u_n6 pour tout entier n0.
Erreurs fréquentes
- Vérifier une propriété pour n=1, 2, 3, , 100 ne la prouve pas pour tout n. Et une hérédité sans initialisation ne prouve rien : « 10^n+1 est divisible par 9 » est héréditaire mais fausse pour tout n.
- Oublier l'initialisation (une hérédité seule ne prouve rien).
- Supposer la propriété « pour tout n » dans l'hérédité (on suppose ce qu'on veut prouver).
- Croire que vérifier quelques valeurs de n suffit.