Le chapitre en bref
Voici un aperçu complet du chapitre Raisonnement par récurrence. Cette page ne traite pas de tout : elle se concentre sur ce qui bloque le plus souvent, l'intérieur de l'hérédité. On décortique cette étape critique pour ne plus jamais bloquer sur une récurrence.
- Le principe de récurrence et sa rédaction développé ci-dessous
Les trois étapes, ce que chacune doit contenir, et les formulations qui valent des points. - Réussir l'hérédité développé ci-dessous
Trouver le chemin du calcul, savoir où l'hypothèse de récurrence s'utilise, et arriver à la cible. - Récurrence et suites : démontrer une formule explicite conjecturée, un encadrement, un sens de variation.
- Récurrence et inégalités : l'inégalité de Bernoulli et les comparaisons de croissance.
- Récurrence double (ou forte) : quand la relation fait intervenir deux rangs à la fois, comme la suite de Fibonacci.
Ces cinq aspects, c'est le chapitre tel qu'il est dans l'app : la fiche de révision pour le cours, et toutes les questions d'entraînement et d'approfondissement corrigées pour les mettre en pratique.
Les trois étapes
Tu les connais déjà, donc on va vite.
- Initialisation Vérifier la propriété au premier rang, celui d'où part l'énoncé. Souvent n = 0, mais pas toujours.
- Hérédité Supposer la propriété vraie à un rang quelconque, et démontrer qu'elle l'est encore au rang suivant.
- Conclusion La phrase qui relie tout : par principe de récurrence, la propriété est vraie à tous les rangs à partir de celui de l'initialisation.
Tu sais donc déjà à quoi ressemble une récurrence, et à quoi elle sert. Le vrai sujet est de décomposer la deuxième étape, l'hérédité, pour ne plus bloquer.
Les trois temps de l'hérédité
Quand on bloque dans une hérédité, ce n'est presque jamais parce qu'on ne sait pas calculer. C'est parce qu'on ne sait pas où aller. On regarde une expression, on sait qu'il faut « utiliser l'hypothèse de récurrence », et on attend l'idée. Elle ne vient pas, et c'est normal : il n'y a rien à trouver. Voici de quoi repérer exactement les étapes à suivre, dans l'ordre.
1. Trois lignes à écrire sans réfléchir, avant de calculer
Avant la moindre ligne de calcul, tu écris toujours les trois mêmes lignes.
- « Soit k un entier naturel » Le rang est fixé et quelconque.
- « Supposons que », suivi de la propriété au rang k C'est la phrase qui introduit l'hypothèse de récurrence. Tu l'as maintenant sous les yeux, puisque tu sais que tu vas devoir t'en servir.
- « Montrons alors que », suivi de la propriété au rang k+1 C'est ton objectif, ce que tu cherches à démontrer. Tu connais maintenant exactement ta cible, et elle va te guider pendant le calcul.
Ces trois lignes ne sont pas une formalité de rédaction posée après coup : le barème leur accorde des points, et les écrire te donne la méthode en même temps que la copie. Attention à la deuxième, c'est là que se joue la première des erreurs classiques : on suppose la propriété vraie à un rang k, jamais « pour tout k ».
Le réflexe : dans une hérédité, tu sais ce que tu dois démontrer (la propriété au rang k+1) et ce que tu dois utiliser (la propriété au rang k). Il ne reste plus qu'à trouver le chemin qui relie les deux.
2. Trouver le lien entre le rang n et le rang n+1
Tu as maintenant un point de départ (le rang k) et un point d'arrivée (le rang k+1). Ce qui les relie est toujours dans l'énoncé, et c'est toujours une seule formule ou une seule phrase, qui fait le lien entre un rang et le suivant. Elle prend trois formes, selon le type d'exercice.
- Une suite La relation de récurrence, un+1 = f(un) : elle dit exactement ce que le rang n+1 doit au rang n.
- Une somme La somme au rang n+1 est celle au rang n, plus un terme de plus. Ce terme se lit dans l'écriture de la somme.
- Une puissance La règle des exposants, 4n+1 = 4 × 4n : elle fait apparaître le rang n à l'intérieur du rang n+1.
Cherche ce lien avant de calculer, pas pendant. Il n'est jamais à inventer : si tu ne le trouves pas, c'est que tu n'as pas fini de lire l'énoncé, pas que tu manques d'idée. Et sans lui, l'hérédité ne peut pas aboutir.
Le réflexe : souligne dans l'énoncé la ligne qui relie deux rangs consécutifs. Dans la plupart des exercices c'est la relation de récurrence, et elle est écrite noir sur blanc dès la première phrase.
3. Partir du bon bout et se laisser porter
Pars du membre qui contient le rang k+1, celui de la cible, et applique le lien. Il transforme mécaniquement une expression du rang k+1 en une expression du rang k. Une fois que tu t'es ramené au rang k, tu es à l'étape critique, le fameux moment où « on utilise l'hypothèse de récurrence » : l'expression dont elle parle vient d'apparaître, et tu la remplaces par ce qu'elle vaut. Ce qui reste ensuite est un court calcul, pour faire apparaître exactement la propriété sous la forme attendue au rang k+1.
Le réflexe : une hérédité ne peut pas se terminer sans que l'hypothèse de récurrence ait servi. Si elle n'a pas servi, soit ton raisonnement est faux ou incomplet, soit tu viens de faire un raisonnement direct qui n'avait pas besoin d'une récurrence.
Les trois temps en résumé
- Temps 1 Rédige les trois lignes mécaniques : soit k, supposons que, montrons alors que.
- Temps 2 Trouve dans l'énoncé le lien entre deux rangs consécutifs, celui qui ramène le rang k+1 au rang k.
- Temps 3 Applique l'hypothèse de récurrence, et termine le calcul jusqu'à la cible.
Trois exemples guidés d'hérédité
Voici les trois formes que prend la question au bac, déroulées en entier. À chaque fois les trois temps apparaissent dans le même ordre et portent les mêmes couleurs, pour que tu voies la méthode se répéter d'une famille à l'autre.
la cible le lien entre les rangs l'hypothèse de récurrence
Une suite, quand la cible est une égalité
Soit la suite définie par u0 = 2 et un+1 = 2un + 3 pour tout entier naturel n. Montrer que un = 5 × 2n − 3.
Hérédité
Soit k un entier naturel. Supposons que hypothèse de récurrence : uk = 5 × 2k − 3.
Temps 1, les deux premières lignes. Le rang est fixé, et l'hypothèse de récurrence est la propriété au rang k, recopiée telle quelle.
Montrons alors que cible : uk+1 = 5 × 2k+1 − 3
Temps 1, troisième ligne. On a remplacé n par k+1 partout, rien de plus. C'est écrit avant de commencer.
uk+1 = lien entre les rangs : 2uk + 3
Temps 2. Le lien, c'est la relation de récurrence de l'énoncé. On part du rang k+1.
uk+1 = 2hypothèse de récurrence : (5 × 2k − 3) + 3
Temps 3. uk vient d'apparaître, donc l'hypothèse s'applique. Il n'y a pas d'autre instant possible.
uk+1 = 10 × 2k − 6 + 3
uk+1 = cible : 5 × 2k+1 − 3
On simplifie, et 10 × 2k vaut 5 × 2k+1. La cible est atteinte, donc on s'arrête.
Regarde le trajet : à aucun moment il n'a fallu deviner. Le rang k+1 a été ramené au rang k par la relation de l'énoncé, l'hypothèse a comblé le trou, et la cible a dit quand s'arrêter.
Une somme, quand le lien est un terme de plus
Montrer que pour tout entier n ≥ 1 : 2 + 4 + 6 + … + 2n = n(n + 1).
Hérédité
Soit k ≥ 1. Supposons que hypothèse de récurrence : 2 + 4 + … + 2k = k(k + 1).
Temps 1, les deux premières lignes.
Montrons alors que cible : 2 + 4 + … + 2k + 2(k + 1) = (k + 1)(k + 2)
Temps 1, troisième ligne. Attention au membre de gauche : au rang k+1 la somme compte un terme de plus, et ce terme s'écrit 2(k + 1).
2 + 4 + … + 2k + 2(k + 1) = lien entre les rangs : (2 + 4 + … + 2k) + 2(k + 1)
Temps 2. Ici le lien n'est pas une formule de l'énoncé, c'est un regroupement : la somme au rang k+1 est celle au rang k, plus le terme suivant.
= hypothèse de récurrence : k(k + 1) + 2(k + 1)
Temps 3. La parenthèse est exactement le membre de gauche de l'hypothèse. On la remplace par ce qu'elle vaut.
= cible : (k + 1)(k + 2)
On factorise par k + 1, le facteur commun aux deux termes, et la cible est atteinte.
La cible a fait le travail deux fois. Elle a dit quel terme ajouter, en montrant ce que le membre de gauche doit contenir au rang k+1 ; puis elle a dit sous quelle forme ranger le résultat, ce qui suggérait de factoriser par k + 1 plutôt que de tout développer.
Une suite, quand la cible est une inégalité
Soit la suite définie par v0 = 0 et vn+1 = (vn + 3)/2 pour tout entier naturel n. Montrer que vn ≤ 3.
Hérédité
Soit k un entier naturel. Supposons que hypothèse de récurrence : vk ≤ 3.
Temps 1, les deux premières lignes. L'hypothèse est ici une inégalité, et c'est toute la différence avec les deux exemples précédents.
Montrons alors que cible : vk+1 ≤ 3
Temps 1, troisième ligne. La cible est courte, ce qui ne la rend pas facultative : sans elle on ne sait pas dans quel sens travailler.
vk+1 = lien entre les rangs : (vk + 3)/2
Temps 2. Le lien, encore la relation de l'énoncé. On est ramené au rang k.
vk+1 ≤ hypothèse de récurrence : (3 + 3)/2
Temps 3. L'hypothèse dit vk ≤ 3, donc on remplace vk par 3 et le signe = devient ≤. Diviser par 2 conserve le sens de l'inégalité, puisque 2 est positif.
cible : vk+1 ≤ 3
Le calcul se termine en une ligne, et la cible est atteinte.
Trois exercices, trois formes différentes, mais pas trois méthodes : le même guide a été appliqué trois fois, dans le même ordre. Les trois lignes d'abord, le lien de l'énoncé ensuite pour se ramener au rang k, puis l'hypothèse de récurrence et un court calcul jusqu'à la cible. Ce qui change d'un exercice à l'autre, c'est la forme du lien, jamais l'ordre des temps.
Le chapitre Raisonnement par récurrence est gratuit dans l'app : la fiche complète et les questions corrigées, sans compte à créer.
Les erreurs classiques
Quatre erreurs reviennent, et aucune n'est une erreur de calcul. Ce sont toutes des erreurs de raisonnement.
1. Supposer la propriété vraie « pour tout k »
L'hypothèse de récurrence porte sur un entier k, fixé et quelconque, pas sur tous à la fois. « Supposons que la propriété soit vraie pour tout k » revient à supposer exactement ce qu'on veut démontrer, et le raisonnement ne vaut plus rien.
2. Ne jamais utiliser l'hypothèse de récurrence
Si le calcul de l'hérédité tient debout sans l'hypothèse, deux cas seulement. Soit la propriété se démontre directement, et la récurrence était inutile depuis le début. Soit, et c'est presque toujours celui-là, le calcul est faux et il a sauté une étape en appliquant au rang k+1 la formule qu'il est censé démontrer.
3. Initialiser au mauvais rang
L'initialisation se fait au rang d'où part l'énoncé, pas au rang qui arrange. Pour une propriété annoncée « pour tout n ≥ 1 », c'est n = 1 et pas n = 0. Et certaines propriétés ne se stabilisent que bien plus loin : 2n ≥ n2 est vraie en 0, 1 et 2, puis fausse en n = 3, où 8 < 9, et n'est vraie sans interruption qu'à partir de n = 4. C'est donc en 4 qu'il faut initialiser, pas en 0.
Le réflexe : entoure la borne de l'énoncé avant de commencer. Le rang d'initialisation y est écrit, et c'est un point qui se perd par distraction plus que par ignorance.
4. Croire que l'hérédité suffit
L'hérédité seule ne démontre rien. Elle dit « si c'est vrai à un rang, c'est vrai au suivant », ce qui ne sert à rien tant qu'aucun rang n'est vrai. La propriété « n = n + 1 » est parfaitement héréditaire, puisqu'en ajoutant 1 des deux côtés on obtient n + 1 = n + 2, et elle est pourtant fausse partout : aucun entier ne l'initialise, et la chaîne de dominos ne démarre jamais.
Teste-toi
Six questions, de l'écriture de l'hypothèse à l'hérédité piégée. Cherche la réponse avant de l'ouvrir : c'est l'effort de rappel qui fait tenir la méthode, pas la relecture.
On veut montrer que vn ≥ 4 pour tout entier naturel n, avec v0 = 7 et vn+1 = (vn + 4)/2. Quelle est l'hypothèse de récurrence au rang k ?
- vk+1 ≥ 4
- vk = 4
- vk ≥ 4
- vk ≥ vk−1
Voir la réponse et la correction
Réponse : C.
L'hypothèse de récurrence est la propriété elle-même, écrite au rang k, et rien de plus. C'est la ligne de départ ; vk+1 ≥ 4 est la ligne d'arrivée, c'est-à-dire la cible.
L'erreur classique ici : la réponse A, qui confond l'hypothèse et la cible. Le temps 1 suffit à s'en prémunir, parce qu'écrire la cible oblige à la distinguer de ce dont on part.
On démontre par récurrence que 1 + 3 + 5 + … + (2n − 1) = n2 pour tout n ≥ 1. Que faut-il obtenir à la fin de l'hérédité ?
- 1 + 3 + … + (2k − 1) + (2k + 1) = (k + 1)2
- 1 + 3 + … + (2k − 1) = k2
- 1 + 3 + … + (2k − 1) + (2k − 1) = (k + 1)2
- 1 + 3 + … + (2k + 1) = k2 + 1
Voir la réponse et la correction
Réponse : A.
On remplace n par k+1 partout, y compris dans le dernier terme de la somme : 2(k + 1) − 1 = 2k + 1. Le membre de droite devient (k + 1)2.
L'erreur classique ici : la réponse C, qui incrémente le rang à droite mais recopie l'ancien dernier terme à gauche. C'est l'erreur la plus fréquente sur les sommes, et le temps 1 la rend visible puisqu'il oblige à réécrire les deux membres.
On pose Sn = 12 + 22 + … + n2. Quel est le lien entre Sk+1 et Sk ?
- Sk+1 = Sk + (k + 1)
- Sk+1 = 2Sk
- Sk+1 = Sk × (k + 1)2
- Sk+1 = Sk + (k + 1)2
Voir la réponse et la correction
Réponse : D.
La somme au rang k+1 contient un terme de plus que celle au rang k, et ce terme est le carré du nouvel indice, donc (k + 1)2. C'est le temps 2 appliqué à une somme : le lien n'est pas dans une formule de l'énoncé, il est dans l'écriture même de la somme.
L'erreur classique ici : la réponse A, qui ajoute le nouvel indice au lieu de son carré. Relis ce que la somme additionne, pas seulement jusqu'où elle va.
Pour montrer que 4n ≥ 3n + 1 pour tout entier naturel n, on suppose 4k ≥ 3k + 1. Par quelle ligne l'hérédité commence-t-elle ?
- 4k+1 = 4k + 4
- 4k+1 = 4 × 4k
- 4k+1 ≥ 3(k + 1) + 1
- 4k+1 = (4k)2
Voir la réponse et la correction
Réponse : B.
Le lien entre le rang k+1 et le rang k est la règle des exposants, c'est le temps 2. C'est elle qui fait apparaître 4k, donc l'expression dont l'hypothèse parle, et la suite s'écrit toute seule.
D'abord l'hypothèse de récurrence, le temps 3 : 4 × 4k ≥ 4(3k + 1).
Puis on termine le calcul : 4(3k + 1) = 12k + 4, et 12k + 4 ≥ 3k + 4 = 3(k + 1) + 1 puisque 9k ≥ 0.
L'erreur classique ici : la réponse C, qui écrit la cible et la prend pour un point de départ. La cible s'annonce avant le calcul, elle n'en est jamais la première ligne.
Un élève propose la démonstration suivante, pour la suite définie par un = 4n + 1.
« On démontre par récurrence que un ≥ 1 pour tout entier naturel n.
Initialisation. u0 = 1, et 1 ≥ 1. La propriété est vraie au rang 0.
Hérédité. Soit k un entier naturel. Supposons la propriété vraie au rang k. Montrons qu'elle est vraie au rang k+1. On a uk+1 = 4(k + 1) + 1 = 4k + 5. Or k ≥ 0, donc 4k + 5 ≥ 5 ≥ 1. La propriété est donc vraie au rang k+1.
Conclusion. D'après le principe de récurrence, un ≥ 1 pour tout entier naturel n. »
Que peut-on dire de cette démonstration ?
- L'hypothèse de récurrence n'a pas servi : le rang k+1 est établi directement.
- L'hérédité est fausse, rien ne justifie que 4k + 5 soit supérieur à 1.
- La démonstration est correcte, la propriété est bien établie par récurrence.
- L'initialisation est au mauvais rang, il fallait la faire au rang 1.
Voir la réponse et la correction
Réponse : A.
Chaque calcul est juste, et pourtant la récurrence ne sert à rien. Pour obtenir uk+1 ≥ 1, l'élève part de 4(k + 1) + 1 et minore directement : à aucun moment il ne se sert de ce qu'il a supposé au rang k. Une hérédité qui se termine sans que l'hypothèse ait servi signale toujours l'une de deux choses, soit le calcul est faux, soit, comme ici, la propriété se démontre directement. Une ligne suffisait : 4n + 1 ≥ 1 dès que n ≥ 0.
L'erreur classique ici : la réponse C, parce que la démonstration est effectivement correcte. Elle l'est, mais ce n'est pas une récurrence pour autant. Annoncer une récurrence et ne jamais se servir de l'hypothèse, c'est avoir fait une démonstration directe sans le dire.
On démontre que n! ≥ 2n−1 pour tout n ≥ 1. L'hérédité s'écrit (k + 1)! = (k + 1) × k! ≥ (k + 1) × 2k−1 ≥ 2 × 2k−1 = 2k. Qu'est-ce qui justifie la seconde inégalité ?
- L'hypothèse de récurrence, appliquée une seconde fois.
- Le fait que k + 1 ≥ 2, puisque k ≥ 1.
- La croissance de la fonction qui à n associe 2n.
- Aucune justification n'est nécessaire, les deux inégalités disent la même chose.
Voir la réponse et la correction
Réponse : B.
La première inégalité est le moment où l'hypothèse sert : on y remplace k! par sa minoration 2k−1. La seconde n'a rien à voir avec elle. Elle minore le facteur k + 1 par 2, ce qui est licite parce que k ≥ 1, et parce que 2k−1 est positif, donc multiplier par ce facteur ne change pas le sens de l'inégalité.
Autrement dit, une hérédité qui vise une inégalité comporte presque toujours une étape après le moment de l'hypothèse, et c'est cette étape que les copies abandonnent. Le temps 1 la rend visible : tant que la cible n'est pas atteinte, le travail n'est pas fini.
L'erreur classique ici : la réponse A, qui attribue à l'hypothèse tout ce qui ressemble à une inégalité dans une hérédité. L'hypothèse ne sert qu'une fois, sur l'expression au rang k.
Extrait de fiche
Le principe et la rédaction attendue, d'après la fiche de révision du chapitre.
- Le principe : pour montrer qu'une propriété est vraie à tous les rangs à partir d'un rang de départ, on vérifie la propriété à ce rang, puis on montre qu'elle se transmet d'un rang au suivant, puis on conclut.
- L'hérédité : soit k un rang supérieur ou égal au rang de départ. On suppose la propriété vraie au rang k, c'est l'hypothèse de récurrence, et on démontre qu'elle est vraie au rang k+1.
- La conclusion : par principe de récurrence, la propriété est vraie pour tout entier n supérieur ou égal au rang de départ.
- Attention : l'initialisation peut demander de vérifier plusieurs rangs de base. Une relation qui fait intervenir deux termes précédents, comme celle de Fibonacci, en demande deux.
Questions fréquentes
Comment savoir quoi faire dans l'hérédité d'une récurrence ?
Tu n'as rien à inventer, le chemin est déjà dans l'énoncé. Écris d'abord ce que tu dois obtenir, c'est-à-dire la propriété au rang n+1. Cherche ensuite dans l'énoncé ce qui relie le rang n+1 au rang n : la relation de récurrence pour une suite, le terme ajouté pour une somme, la règle des exposants pour une puissance. Applique ce lien en partant du rang n+1, et l'expression du rang n apparaît d'elle-même : c'est là que l'hypothèse de récurrence sert. En savoir plus →
Où utilise-t-on l'hypothèse de récurrence dans le calcul ?
À un seul endroit, et il se reconnaît : le moment où l'expression au rang n apparaît dans ton calcul. Tu ne décides pas de placer l'hypothèse, tu constates qu'elle est devenue applicable, et tu remplaces cette expression par ce que l'hypothèse dit qu'elle vaut. Si tu arrives au bout de l'hérédité sans avoir utilisé l'hypothèse, relis ton calcul : le plus souvent il est faux et il a sauté une étape.
Quelles formulations utiliser pour rédiger une récurrence ?
Trois phrases suffisent, et elles rapportent des points. « Soit k un entier naturel. Supposons que P(k) soit vraie » introduit l'hypothèse de récurrence, sur un rang fixé et quelconque, jamais sur tous les rangs à la fois. « Montrons alors que P(k+1) est vraie » annonce la cible avant le calcul. « La propriété est vraie au rang de départ et elle est héréditaire, donc par principe de récurrence elle est vraie pour tout entier à partir de ce rang » referme la démonstration sur les deux étapes, et pas sur la seule hérédité.
Le chapitre t'attend en entier dans l'app : la fiche de révision complète, toutes les questions d'entraînement et d'approfondissement corrigées qui s'adaptent à ton niveau, et les annales du bac. La récurrence fait partie des 10 chapitres gratuits.