Karamö, le prof virtuelLeçon 22 sur 33
Raisonnement par récurrence
Je sais démontrer qu'une propriété est vraie pour tous les entiers naturels à partir d'un rang, en rédigeant proprement l'initialisation, l'hérédité et la conclusion.
- 1 h
- 5 exercices corrigés
- 1 schéma
- QCM de 5 questions
À la fin de la leçon, tu sauras :
- Comprendre le principe de la récurrence (effet domino)
- Rédiger une démonstration par récurrence en trois étapes
- Démontrer une égalité portant sur une somme
- Démontrer une inégalité ou une formule explicite pour une suite définie par récurrence
Avant de commencer : Le calcul littéral (développer, factoriser, réduire au même dénominateur), les puissances, la notion de suite vue en classe de Première.
1Je découvre
Pendant la fête de fin d'année d'une école de Kissidougou, les élèves alignent des dominos sur une longue table. Ibrahima pousse le premier : tous tombent, l'un après l'autre, jusqu'au bout de la table.
Pour être sûr que tous les dominos tomberont, pas besoin de les surveiller un par un. Il suffit de vérifier deux choses :
- le premier domino tombe ;
- les dominos sont placés de sorte que si l'un tombe, il fait tomber le suivant.
Le même raisonnement sert en mathématiques. Fanta remarque que 1 = 12, 1 + 3 = 4 = 22, 1 + 3 + 5 = 9 = 32, 1 + 3 + 5 + 7 = 16 = 42. Elle devine que la somme des n premiers nombres impairs vaut toujours n2. Mais vérifier 4, 10 ou même 1 000 cas ne prouve rien pour tous les entiers.
Comment démontrer qu'une propriété est vraie pour tous les entiers naturels, sans les vérifier un par un ?
2Je comprends
1. Le principe de récurrence
Soit P(n) une propriété qui dépend d'un entier naturel n, et n0 un entier naturel. Si :
- Initialisation : P(n0) est vraie ;
- Hérédité : pour tout entier k ≥ n0, si P(k) est vraie, alors P(k + 1) est vraie ;
alors P(n) est vraie pour tout entier n ≥ n0.
L'hypothèse « P(k) est vraie » utilisée dans l'hérédité s'appelle l'hypothèse de récurrence. On ne la démontre pas : on la suppose, et on s'en sert pour prouver P(k + 1).
- 1Initialisation : je vérifie que la propriété est vraie pour le premier entier n₀ (on calcule les deux membres séparément).
- 2Hypothèse de récurrence : je suppose la propriété vraie pour un entier k ≥ n₀ quelconque.
- 3Hérédité : en utilisant cette hypothèse, je démontre la propriété au rang k + 1.
- 4Conclusion : la propriété est vraie au rang n₀ et héréditaire, donc vraie pour tout n ≥ n₀.
2. Démontrer une égalité sur une somme
Exemple
Démontrer que, pour tout entier n ≥ 1 : 1 + 3 + 5 + … + (2n − 1) = n².
Soit P(n) : « 1 + 3 + … + (2n − 1) = n² ».
Initialisation (n = 1) : le membre de gauche vaut 1 ; le membre de droite vaut 1² = 1. P(1) est vraie.
Hérédité : soit k ≥ 1. On suppose P(k) vraie : 1 + 3 + … + (2k − 1) = k².
On veut montrer P(k + 1) : 1 + 3 + … + (2k − 1) + (2k + 1) = (k + 1)².
(Le nombre impair suivant 2k − 1 est 2(k + 1) − 1 = 2k + 1.)
1 + 3 + … + (2k − 1) + (2k + 1) = k² + (2k + 1) (hypothèse de récurrence)
= k² + 2k + 1 = (k + 1)².
P(k + 1) est vraie.
Conclusion : P(1) est vraie et P est héréditaire, donc pour tout n ≥ 1, 1 + 3 + … + (2n − 1) = n².
Exemple
Démontrer que, pour tout n ≥ 1 : 1 + 2 + … + n = n(n + 1)/2.
Initialisation : pour n = 1, à gauche 1 ; à droite 1 × 2 / 2 = 1. Vrai.
Hérédité : on suppose 1 + 2 + … + k = k(k + 1)/2. Alors
1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2.
C'est bien la formule au rang k + 1.
Conclusion : la formule est vraie pour tout n ≥ 1.
Application : la somme des entiers de 1 à 100 vaut 100 × 101 / 2 = 5 050.
3. Démontrer une inégalité
Exemple
Démontrer que, pour tout entier naturel n : 2ⁿ ≥ n + 1.
Initialisation (n = 0) : 2⁰ = 1 et 0 + 1 = 1 ; 1 ≥ 1 est vrai.
Hérédité : on suppose 2ᵏ ≥ k + 1 pour un entier k ≥ 0.
On multiplie par 2 (positif) : 2ᵏ⁺¹ ≥ 2k + 2.
Or 2k + 2 = (k + 2) + k ≥ k + 2, car k ≥ 0.
Donc 2ᵏ⁺¹ ≥ k + 2 = (k + 1) + 1. La propriété est vraie au rang k + 1.
Conclusion : pour tout entier naturel n, 2ⁿ ≥ n + 1.
4. Suites définies par récurrence
Une suite peut être définie par son premier terme et une relation entre un terme et le suivant, par exemple u0 = 2 et un+1 = 2un - 1. On calcule : u1 = 3, u2 = 5, u3 = 9, u4 = 17. On devine que un = 2n + 1 ; la récurrence permet de le prouver.
Exemple
Soit u₀ = 2 et u(n+1) = 2u(n) − 1. Démontrer que u(n) = 2ⁿ + 1 pour tout n.
Initialisation : u₀ = 2 et 2⁰ + 1 = 2. Vrai.
Hérédité : on suppose u(k) = 2ᵏ + 1. Alors
u(k+1) = 2u(k) − 1 = 2(2ᵏ + 1) − 1 = 2ᵏ⁺¹ + 2 − 1 = 2ᵏ⁺¹ + 1.
C'est la formule au rang k + 1.
Conclusion : pour tout entier naturel n, u(n) = 2ⁿ + 1.
Méthode
Pour rédiger une récurrence sans erreur :
- J'écris clairement la propriété P(n) avec des guillemets.
- Initialisation : je calcule SÉPARÉMENT le membre de gauche et le membre de droite pour n₀.
- Hérédité : j'écris « Soit k ≥ n₀ ; on suppose P(k) vraie » puis j'écris ce que je veux obtenir, P(k + 1).
- Je pars de l'expression au rang k + 1 et je fais apparaître l'expression du rang k pour utiliser l'hypothèse.
- Je calcule jusqu'à obtenir exactement P(k + 1).
- Conclusion : « P(n₀) est vraie et P est héréditaire, donc P(n) est vraie pour tout n ≥ n₀. »
3Je retiens
Je retiens
Récurrence : initialisation (P(n₀) vraie) + hérédité (P(k) ⇒ P(k + 1)) ⇒ P(n) vraie pour tout n ≥ n₀.
L'hypothèse de récurrence est supposée, jamais démontrée ; elle doit être UTILISÉE dans l'hérédité.
1 + 2 + … + n = n(n + 1)/2 ; 1 + 3 + … + (2n − 1) = n².
Dans l'hérédité, on part du rang k + 1 et on fait apparaître le rang k.
Vérifier quelques cas ne suffit jamais : il faut les deux étapes.
Toujours finir par une phrase de conclusion.
4Erreurs fréquentes
- Oublier l'initialisation : une propriété fausse peut être héréditaire. Exemple : « n + 1 ≤ n ». Si k + 1 ≤ k, alors en ajoutant 1, k + 2 ≤ k + 1 : l'hérédité marche, mais la propriété n'est vraie pour aucun entier, car l'initialisation échoue.
- Supposer ce qu'on veut démontrer : on suppose P(k), pas « P(n) pour tout n ».
- Faire l'hérédité sans utiliser l'hypothèse de récurrence : si elle ne sert pas, il y a une erreur.
- Mal écrire le terme au rang k + 1 : le terme impair suivant 2k − 1 est 2k + 1, et non 2k.
5Je m’exerce
1Exercice 1
Démontre par récurrence que, pour tout entier n ≥ 1 :
2 + 4 + 6 + … + 2n = n(n + 1).
Voir le corrigéCacher le corrigé
Soit P(n) : « 2 + 4 + … + 2n = n(n + 1) ».
Initialisation (n = 1) : à gauche 2 ; à droite 1 × 2 = 2. P(1) est vraie.
Hérédité : soit k ≥ 1 ; on suppose 2 + 4 + … + 2k = k(k + 1). Alors
2 + 4 + … + 2k + 2(k + 1) = k(k + 1) + 2(k + 1) = (k + 1)(k + 2).
C'est P(k + 1).
Conclusion : P(1) est vraie et P est héréditaire, donc pour tout n ≥ 1, 2 + 4 + … + 2n = n(n + 1).
2Exercice 2
Démontre par récurrence que, pour tout entier naturel n :
1 + 2 + 22 + … + 2n = 2n + 1 - 1.
Voir le corrigéCacher le corrigé
Soit P(n) : « 1 + 2 + … + 2n = 2n+1 - 1 ».
Initialisation (n = 0) : à gauche 20 = 1 ; à droite 21 - 1 = 1. P(0) est vraie.
Hérédité : soit k ≥ 0 ; on suppose 1 + 2 + … + 2k = 2k+1 - 1. Alors
1 + 2 + … + 2k + 2k+1 = 2k+1 - 1 + 2k+1 = 2 × 2k+1 - 1 = 2k+2 - 1.
C'est P(k + 1).
Conclusion : pour tout entier naturel n, 1 + 2 + … + 2n = 2n+1 - 1.
3Exercice 3
Soit la suite définie par u0 = 0 et un+1 = un + 2n + 1.
a) Calcule u1, u2, u3 et u4. Que conjectures-tu ?
b) Démontre ta conjecture par récurrence.
Voir le corrigéCacher le corrigé
a) u1 = 0 + 0 + 1 = 1 ; u2 = 1 + 2 + 1 = 4 ; u3 = 4 + 4 + 1 = 9 ; u4 = 9 + 6 + 1 = 16. On conjecture un = n2.
b) Initialisation : u0 = 0 = 02. Vrai.
Hérédité : on suppose uk = k2. Alors uk+1 = uk + 2k + 1 = k2 + 2k + 1 = (k + 1)2.
Conclusion : pour tout entier naturel n, un = n2.
4Exercice 4
Soit la suite définie par u0 = 2 et un+1 = 12un + 3.
a) Calcule u1 et u2.
b) Démontre par récurrence que, pour tout entier naturel n, un ≤ 6.
c) Démontre que un+1 - un = 3 - 12un et déduis-en que la suite est croissante.
Voir le corrigéCacher le corrigé
a) u1 = 12 × 2 + 3 = 4 ; u2 = 12 × 4 + 3 = 5.
b) Soit P(n) : « un ≤ 6 ».
Initialisation : u0 = 2 ≤ 6. Vrai.
Hérédité : on suppose uk ≤ 6. Alors 12uk ≤ 3, donc 12uk + 3 ≤ 6, c'est-à-dire uk+1 ≤ 6.
Conclusion : pour tout entier naturel n, un ≤ 6.
c) un+1 - un = 12un + 3 - un = 3 - 12un. Comme un ≤ 6, on a 12un ≤ 3, donc 3 - 12un ≥ 0. Ainsi un+1 ≥ un pour tout n : la suite est croissante.
5Exercice 5
(Type BAC) Mariama dépose 500 000 GNF sur un compte d'épargne à Labé. Chaque année, le compte rapporte 5 % d'intérêts, puis elle ajoute 100 000 GNF. On note Cn le capital, en GNF, après n années ; C0 = 500 000.
a) Justifie que Cn+1 = 1,05 Cn + 100 000 et calcule C1 et C2.
b) Démontre par récurrence que, pour tout entier naturel n : Cn = 2 500 000 × 1,05n - 2 000 000.
c) Calcule le capital au bout de 10 ans (arrondi au franc près ; on donne 1,0510 ≈ 1,628895).
Voir le corrigéCacher le corrigé
a) Chaque année, le capital est multiplié par 1,05 (intérêts de 5 %), puis augmenté de 100 000 GNF : Cn+1 = 1,05 Cn + 100 000.
C1 = 1,05 × 500 000 + 100 000 = 525 000 + 100 000 = 625 000 GNF.
C2 = 1,05 × 625 000 + 100 000 = 656 250 + 100 000 = 756 250 GNF.
b) Soit P(n) : « Cn = 2 500 000 × 1,05n - 2 000 000 ».
Initialisation : 2 500 000 × 1 - 2 000 000 = 500 000 = C0. Vrai.
Hérédité : on suppose Ck = 2 500 000 × 1,05k - 2 000 000. Alors
Ck+1 = 1,05 Ck + 100 000 = 1,05 × 2 500 000 × 1,05k - 1,05 × 2 000 000 + 100 000
= 2 500 000 × 1,05k+1 - 2 100 000 + 100 000 = 2 500 000 × 1,05k+1 - 2 000 000.
C'est P(k + 1).
Conclusion : pour tout entier naturel n, Cn = 2 500 000 × 1,05n - 2 000 000.
Contrôle : pour n = 1, 2 500 000 × 1,05 - 2 000 000 = 625 000, comme en a).
c) C10 ≈ 2 500 000 × 1,628895 - 2 000 000 = 4 072 237,5 - 2 000 000 ≈ 2 072 237 GNF (le calcul exact à la calculatrice donne environ 2 072 236,57, soit 2 072 237 GNF au franc près).
Cherche d’abord seul, sur ton cahier, puis ouvre le corrigé pour comparer.
6Je vérifie
Choisis une réponse pour chaque question : la correction s’affiche aussitôt.
Crée ton compte élève gratuit pour cocher les leçons terminées, suivre ta progression et gagner des points au QCM.
