Démontrer par récurrence
Les trois blocs de la rédaction, l'hypothèse de récurrence et les deux formes d'hérédité, en 5 étapes progressives : Terminale spécialité.
Le raisonnement par récurrence se rédige toujours de la même façon, en trois blocs : initialisation, hérédité, conclusion. Ce qui bloque n'est presque jamais le calcul, mais deux choses précises : écrire correctement l'hypothèse de récurrence, et savoir par quoi commencer l'hérédité. Cette fiche découpe la compétence en 5 étapes, et se termine par deux sujets types de devoir surveillé, entièrement corrigés. Elle commence par un atelier de dominos manipulable : c'est en cassant la chaîne qu'on comprend pourquoi les deux conditions sont indispensables. Et dans chaque hérédité rédigée, l'HR est écrite noir sur blanc, puis son point d'utilisation est signalé : c'est la marque d'une preuve correcte.
Un parcours en 5 étapes, du plus simple au plus costaud :
- 1 Je sais énoncer la propriété et vérifier l'initialisation.
- 2 Je sais écrire l'hypothèse de récurrence, et ce qu'il reste à démontrer.
- 3 Je sais mener l'hérédité quand la propriété est une égalité.
- 4 Je sais mener l'hérédité quand la propriété est une inégalité.
- 5 Je sais rédiger la conclusion et choisir un indice qui ne crée pas de confusion.
Rappels indispensables
Une propriété P(n) est héréditaire à partir d'un rang si, dès qu'elle est vraie pour un entier k, elle est encore vraie pour l'entier k+1. Image : des dominos alignés, réglés pour que chacun renverse le suivant.
Principe du raisonnement par récurrence : si la propriété est vraie au premier rang (initialisation) ET héréditaire à partir de ce rang (hérédité), alors elle est vraie pour tout entier à partir de ce rang (conclusion).
Le schéma des dominos : pourquoi DEUX conditions ?
Une récurrence, c'est une rangée de dominos :
- Initialisation = on pousse le premier ;
- Hérédité = chaque domino est assez près du suivant pour le renverser.
Une rangée qui tombe bien ne t'apprend pas grand-chose. Ce qui fait comprendre, c'est de casser la chaîne : écarte un domino, ou refuse de pousser le premier, et regarde ce qui reste debout.
① Les deux conditions. On pousse le premier et chaque domino atteint le suivant : la chute se propage de proche en proche et n'a aucune raison de s'arrêter. P(n) est vraie pour tout n.
② Personne ne pousse le premier (initialisation manquante). L'hérédité est pourtant parfaite : chaque domino renverserait le suivant. Mais rien ne tombe, et aucun rang n'est démontré. Une hérédité seule ne dit que ceci : « si l'un tombe, le suivant tombe ». Elle ne dit jamais qu'un seul tombe.
③ Un domino trop écarté (hérédité en défaut). On a bien poussé le premier, mais l'implication P(k) \Rightarrow P(k+1) est fausse à un rang : la chute s'arrête net et tout ce qui suit reste debout. Un seul rang qui casse suffit à ruiner toute la suite.
À retenir : l'initialisation dit que ça part, l'hérédité dit que ça continue. Il faut les deux, et il faut l'hérédité à tous les rangs à partir du premier.
Étape 1 : Énoncer la propriété et faire l'initialisation
👆 À toi de jouer
- La suite (u_n) est définie par u_0 = 0 et u_{n+1} = 3u_n - 2. Vérifier l'initialisation de la propriété {u_n = 1 - 3^n} au rang 0.
Voir la réponse
D'un côté u_0 = 0. De l'autre \begin{aligned}1 - 3^0 &= 1 - 1 \\ &= 0\end{aligned} Les deux membres sont égaux, donc la propriété est vraie au rang 0.
Étape 2 : Écrire l'hypothèse de récurrence (l'HR)
Le gabarit de l'hérédité, à recopier tel quel
Soit k un entier fixé, k \geqslant n_0. Supposons P(k) vraie, c'est-à-dire : \ldots HR
🎯 Démontrons alors P(k+1), c'est-à-dire : \ldots
Ces deux lignes se rédigent avant tout calcul. Écrire le but permet de savoir vers quoi on va : sans lui, on transforme au hasard.
👆 À toi de jouer
- Pour la propriété {u_n = 1 - 3^n}, écrire l'hypothèse de récurrence au rang k, puis ce qu'il reste à démontrer.
Voir la réponse
Soit k \in \mathbb{N}. On suppose {u_k = 1 - 3^k} HR
Ce qu'il faut démontrer : {u_{k+1} = 1 - 3^{k+1}}.
Les deux pièges : ne pas écrire « pour tout k » (ce serait supposer le résultat), et ne pas oublier d'écrire le but : c'est lui qui dit quand s'arrêter.
Étape 3 : L'hérédité quand la propriété est une égalité
👆 À toi de jouer
- Démontrer l'hérédité pour {u_n = 1 - 3^n}, avec u_{n+1} = 3u_n - 2.
Voir la réponse
On part de u_{k+1}, que la relation de récurrence exprime avec u_k :Hypothèse de récurrence
Soit k \in \mathbb{N}. On suppose P(k) vraie, c'est-à-dire u_k = 1 - 3^{k}. HR
🎯 Démontrons P(k+1), c'est-à-dire {u_{k+1} = 1 - 3^{k+1}}.
\begin{aligned} u_{k+1} &= 3u_k - 2 \\ &= 3\,\underbrace{\left(1 - 3^{k}\right)}_{\text{par HR}} - 2 \\ &= 3 - 3 \times 3^{k} - 2 \\ &= 3 - 3^{k+1} - 2 \\ &= 1 - 3^{k+1} \end{aligned}HR Où l'HR a-t-elle servi ? À la 2e ligne, quand u_k a été remplacé par 1 - 3^{k}. C'est le seul endroit : sans l'HR, on ne saurait rien de u_k et le calcul s'arrêterait à la première ligne. Tout le reste n'est que du calcul ordinaire.
La forme obtenue est exactement celle attendue : P(k+1) est vraie.
Étape 4 : L'hérédité quand la propriété est une inégalité
👆 À toi de jouer
- On suppose 3^k \geqslant 1 + 2k. Démontrer que {3^{k+1} \geqslant 1 + 2(k+1)}.
Voir la réponse
La propriété est une inégalité : on part de l'HR et on la transforme. On multiplie ses deux membres par 3, qui est strictement positif, donc le sens ne change pas :Hypothèse de récurrence
Soit k \in \mathbb{N}. On suppose 3^{k} \geqslant 1 + 2k. HR
🎯 Démontrons {3^{k+1} \geqslant 1 + 2(k+1)}, c'est-à-dire 3^{k+1} \geqslant 2k + 3.
\begin{aligned} 3^{k+1} &= 3 \times 3^{k} \\ &\geqslant 3\,\underbrace{(1 + 2k)}_{\text{par HR}} \\ &= 6k + 3 \end{aligned}HR Où l'HR a-t-elle servi ? À la 2e ligne, quand 3^{k} a été minoré par 1 + 2k. C'est aussi l'endroit où le signe = devient \geqslant : à partir de là, on ne fait plus que minorer.
L'écart à combler (le vrai travail) : on est arrivé à 6k + 3, mais le but est 2k + 3. Il suffit donc de montrer que {6k + 3 \geqslant 2k + 3} :
(6k + 3) - (2k + 3) = 4k \geqslant 0 \quad \text{car } k \geqslant 0.
Par transitivité : 3^{k+1} \geqslant 6k + 3 \geqslant 2k + 3 = 1 + 2(k+1) Donc P(k+1) est vraie.
⚖️ Par où commencer l'hérédité ? La question qui revient tout le temps
« Pour une inégalité, on commence direct par l'HR, j'ai bon ? » Oui : c'est exactement la bonne habitude. Mais elle ne se transpose pas aux égalités, où la marche est différente.
Inégalité : on PART de l'HR
- On écrit l'HR.
- On la transforme : ajouter un même nombre aux deux membres, multiplier par un nombre strictement positif.
- On arrive près du but, et on comble l'écart.
Égalité : on ARRIVE à l'HR
- On part d'un membre de P(k+1) (la somme jusqu'à k+1, ou u_{k+1}).
- On isole le dernier terme, ou on applique la relation de récurrence.
- On injecte l'HR à la place de ce qu'elle décrit, puis on transforme jusqu'à l'autre membre.
⚠️ Deux réserves sur les inégalités, et ce sont elles qui coûtent des points :
- multiplier les deux membres par un nombre négatif renverse le sens de l'inégalité (et par 0, elle devient une égalité) : on ne multiplie que par du strictement positif ;
- on n'atterrit presque jamais pile sur l'inégalité voulue : il reste un écart à combler. C'est la phrase « il suffit de montrer que … \geqslant … », et c'est là qu'est le vrai travail, pas dans la multiplication.
La formulation à retenir : ce qui est universel, ce n'est pas « partir de l'HR », c'est s'en servir et le dire. Une hérédité où l'on ne voit pas où l'HR intervient n'est pas une démonstration par récurrence : c'est un calcul.
Étape 5 : Conclure, et choisir le bon indice
Un dernier réflexe : l'indice de l'hérédité ne doit jamais entrer en conflit avec un indice déjà utilisé dans l'énoncé. On prend k d'habitude, mais si k sert déjà (par exemple comme indice de sommation dans un \sum), on prend p.
👆 À toi de jouer
- Dans la propriété \sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}, quel indice choisir pour mener l'hérédité, et pourquoi ?
Voir la réponse
Surtout pas k : il est déjà pris comme indice de sommation, et le réutiliser rendrait la rédaction incompréhensible. On mène donc l'hérédité avec p : on suppose P(p) vraie, c'est-à-dire \sum_{k=1}^{p} k = \dfrac{p(p+1)}{2} HR, et on démontre P(p+1). L'HR garde bien son k de sommation à l'intérieur du \sum : ce sont deux lettres différentes, et c'est justement pour cela qu'il ne faut pas les confondre.
👆 À toi de jouer : type devoir surveillé
- La suite (u_n) est définie par u_0 = 0 et u_{n+1} = 3u_n - 2 pour tout n \in \mathbb{N}. Démontrer par récurrence que pour tout n \in \mathbb{N} : {u_n = 1 - 3^n}.
Voir la réponse
Initialisation. D'un côté u_0 = 0 ; de l'autre \begin{aligned}1 - 3^0 &= 1 - 1 \\ &= 0\end{aligned} Les deux membres sont égaux, donc P(0) est vraie.
Hérédité. Soit k \in \mathbb{N}. Supposons P(k) vraie, c'est-à-dire {u_k = 1 - 3^k} HR. Démontrons alors P(k+1), c'est-à-dire {u_{k+1} = 1 - 3^{k+1}}.
\begin{aligned} u_{k+1} &= 3u_k - 2 \\ &= 3\,\underbrace{\left(1 - 3^{k}\right)}_{\text{par HR}} - 2 \\ &= 3 - 3 \times 3^{k} - 2 \\ &= 3 - 3^{k+1} - 2 \\ &= 1 - 3^{k+1} \end{aligned}
HR utilisée à la 2e ligne : c'est elle qui donne le droit de remplacer u_k.
Donc P(k+1) est vraie.
Conclusion. La propriété est vraie au rang 0 et héréditaire à partir de ce rang. Donc, d'après le principe de récurrence, {u_n = 1 - 3^n} pour tout n \in \mathbb{N}. ∎ - Démontrer par récurrence que pour tout entier n \geqslant 1 : \sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}.
Voir la réponse
L'indice k est déjà l'indice de sommation : on mène l'hérédité avec p.
Initialisation. Pour n = 1 : \sum_{k=1}^{1} k = 1, et \begin{aligned}\dfrac{1 \times (1+1)}{2} &= \dfrac{2}{2} \\ &= 1\end{aligned} Les deux membres sont égaux, donc la propriété est vraie au rang 1.
Hérédité. Soit p \geqslant 1. Supposons P(p) vraie, c'est-à-dire \sum_{k=1}^{p} k = \dfrac{p(p+1)}{2} HR. Démontrons alors P(p+1), c'est-à-dire \sum_{k=1}^{p+1} k = \dfrac{(p+1)(p+2)}{2}.
C'est une égalité : on part du membre de gauche de P(p+1), on isole le dernier terme, puis on y injecte l'HR.
\begin{aligned} \sum_{k=1}^{p+1} k &= \left(\sum_{k=1}^{p} k\right) + (p+1) \\ &= \underbrace{\dfrac{p(p+1)}{2}}_{\text{par HR}} + (p+1) \\ &= \dfrac{p(p+1) + 2(p+1)}{2} \\ &= \dfrac{(p+1)(p+2)}{2} \end{aligned}
HR utilisée à la 2e ligne, une fois le dernier terme mis à part : c'est tout l'intérêt de l'isoler, car l'HR ne parle que de la somme jusqu'à p.
Donc P(p+1) est vraie.
Conclusion. La propriété est vraie au rang 1 et héréditaire à partir de ce rang. Donc, d'après le principe de récurrence, \sum_{k=1}^{n} k = \dfrac{n(n+1)}{2} pour tout entier n \geqslant 1. ∎
Fiche compétences rédigée par Logimaths.