Contrôle qui arrive et tu n'as jamais entendu parler de récurrence? Pas de panique. On va partir des deux seules choses dont tu as vraiment besoin pour démarrer: savoir ce qu'est une suite arithmétique et une suite géométrique. Ensuite, on t'explique le principe en deux mots, et tu vas voir que c'est juste une histoire de dominos. Tu vas même faire tes premiers petits exercices (avec des trous, on te tient la main).
Prérequis éclairs: suites vues en première
Avant de parler de récurrence, on réactive deux outils de première. Une suite arithmétique de raison $r$ : pour passer d'un terme au suivant, on ajoute $r$. Par exemple $u_{n+1}=u_n+3$.
Une suite géométrique de raison $q$ : pour passer d'un terme au suivant, on multiplie par $q$. Par exemple $v_{n+1}=2\,v_n$.
Pour l'instant, pas besoin de plus. On garde juste en tête qu'on sait passer de $n$ à $n+1$ grâce à une opération simple.
Le raisonnement par récurrence, version ultra-condensée
Le raisonnement par récurrence sert à prouver qu'une propriété $P(n)$ est vraie pour tous les entiers $n$ à partir d'un certain rang.
On fait comme avec des dominos:
Initialisation: on fait tomber le premier domino, autrement dit on vérifie que $P(n_0)$ est vraie.
Hérédité: on prouve que si un domino quelconque tombe, alors le suivant tombe aussi, autrement dit on montre que si $P(n)$ est vraie, alors $P(n+1)$ est vraie.
Conclusion: on dit «puisque le premier tombe et que chaque fois qu'un domino tombe le suivant tombe, alors tous les dominos tombent». En langage mathématique: «Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq n_0$».
En rédaction, on distingue bien les trois étapes. Au début, on écrit clairement ce qu'est $P(n)$. Par exemple, pour prouver que $1+2+\dots+n=\frac{n(n+1)}{2}$, on pose $P(n):\;\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$.
À toi de jouer
1. On veut démontrer par récurrence que pour tout $n\in\mathbb{N}$, $\displaystyle\sum_{k=0}^{n}3^k = \frac{3^{n+1}-1}{2}$. Pour cela, on pose $P(n):\;\sum_{k=0}^{n}3^k = \dfrac{3^{n+1}-1}{2}$.
Initialisation (n=0): $\sum_{k=0}^{0}3^k = \underline{\hspace{1.1em}}$ $\dfrac{3^{0+1}-1}{2} = \dfrac{\underline{\hspace{1.1em}}-1}{2} = \dfrac{\underline{\hspace{1.1em}}}{2} = \underline{\hspace{1.1em}}$ Les deux membres sont égaux, donc $P(0)$ est vraie.
Hérédité: On suppose qu'il existe un entier $n\geq 0$ tel que $P(n)$ est vraie, c'est-à-dire: $\displaystyle\sum_{k=0}^{n}3^k = \underline{\hspace{1.1em}}$ (c'est l'hypothèse de récurrence). On veut prouver $P(n+1)$, c'est-à-dire: $\displaystyle\sum_{k=0}^{n+1}3^k = \dfrac{3^{n+2}-1}{2}$. $\displaystyle\sum_{k=0}^{n+1}3^k = \displaystyle\sum_{k=0}^{n}3^k + \underline{\hspace{1.1em}} = \dfrac{3^{n+1}-1}{2} + \underline{\hspace{1.1em}} = \dfrac{3^{n+1}-1 + 2\times \underline{\hspace{1.1em}}}{2} = \dfrac{\underline{\hspace{1.1em}}\times 3^{n+1} -1}{2} = \dfrac{3^{n+2}-1}{2}$ Donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ est vraie et pour tout $n$, $P(n)\Rightarrow P(n+1)$ est vraie, donc par le principe de récurrence, pour tout $n\in\mathbb{N}$, $\underline{\hspace{1.1em}}$.
Corrigé
On veut démontrer par récurrence que pour tout $n\in\mathbb{N}$, $\displaystyle\sum_{k=0}^{n}3^k = \frac{3^{n+1}-1}{2}$. Pour cela, on pose $P(n):\;\sum_{k=0}^{n}3^k = \dfrac{3^{n+1}-1}{2}$.
Initialisation (n=0): $\sum_{k=0}^{0}3^k = 3^0 = 1$ $\dfrac{3^{0+1}-1}{2} = \dfrac{3-1}{2} = \dfrac{2}{2} = 1$ Les deux membres sont égaux, donc $P(0)$ est vraie.
Hérédité: On suppose qu'il existe un entier $n\geq 0$ tel que $P(n)$ est vraie, c'est-à-dire: $\displaystyle\sum_{k=0}^{n}3^k = \dfrac{3^{n+1}-1}{2}$ (c'est l'hypothèse de récurrence). On veut prouver $P(n+1)$, c'est-à-dire: $\displaystyle\sum_{k=0}^{n+1}3^k = \dfrac{3^{n+2}-1}{2}$. $\displaystyle\sum_{k=0}^{n+1}3^k = \displaystyle\sum_{k=0}^{n}3^k + 3^{n+1} = \dfrac{3^{n+1}-1}{2} + 3^{n+1} = \dfrac{3^{n+1}-1 + 2\times 3^{n+1}}{2} = \dfrac{3\times 3^{n+1} -1}{2} = \dfrac{3^{n+2}-1}{2}$ Donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ est vraie et pour tout $n$, $P(n)\Rightarrow P(n+1)$ est vraie, donc par le principe de récurrence, pour tout $n\in\mathbb{N}$, $\sum_{k=0}^{n}3^k = \dfrac{3^{n+1}-1}{2}$.
2. On veut démontrer par récurrence que pour tout $n\geq 1$, $5^n\geq 4n+1$. On pose $P(n):\;5^n\geq 4n+1$.
Initialisation (n=1): $5^1 = \underline{\hspace{1.1em}}$ et $4\times 1+1 = \underline{\hspace{1.1em}}$. On a bien $\underline{\hspace{1.1em}} \geq \underline{\hspace{1.1em}}$, donc $P(1)$ est vraie.
Hérédité: On suppose qu'il existe $n\geq 1$ tel que $P(n)$ est vraie, c'est-à-dire: $\underline{\hspace{1.1em}}$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire: $5^{n+1}\geq 4(n+1)+1 = \underline{\hspace{1.1em}}$. $5^{n+1} = 5\times 5^n \geq 5\times (\underline{\hspace{1.1em}})$ d'après l'hypothèse de récurrence. Donc $5^{n+1}\geq 5(4n+1) = 20n+5$. Or $20n+5 - (4n+5) = \underline{\hspace{1.1em}}\, n \geq \underline{\hspace{1.1em}}$ car $n\geq 1$. Ainsi $20n+5 \geq 4n+5$, donc $5^{n+1}\geq 4n+5$ et $P(n+1)$ est vraie.
Conclusion: [À compléter]
Corrigé
On veut démontrer par récurrence que pour tout $n\geq 1$, $5^n\geq 4n+1$. On pose $P(n):\;5^n\geq 4n+1$.
Initialisation (n=1): $5^1 = 5$ et $4\times 1+1 = 5$. On a bien $5 \geq 5$, donc $P(1)$ est vraie.
Hérédité: On suppose qu'il existe $n\geq 1$ tel que $P(n)$ est vraie, c'est-à-dire: $5^n \geq 4n+1$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire: $5^{n+1}\geq 4(n+1)+1 = 4n+5$. $5^{n+1} = 5\times 5^n \geq 5\times (4n+1)$ d'après l'hypothèse de récurrence. Donc $5^{n+1}\geq 5(4n+1) = 20n+5$. Or $20n+5 - (4n+5) = 16n \geq 0$ car $n\geq 1$. Ainsi $20n+5 \geq 4n+5$, donc $5^{n+1}\geq 4n+5$ et $P(n+1)$ est vraie.
Conclusion: $P(1)$ est vraie, et pour tout $n\geq 1$, $P(n)\Rightarrow P(n+1)$ est vraie. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq 1$, soit $5^n \geq 4n+1$ pour tout $n\geq 1$.
3. Associe à chaque étape son rôle dans le raisonnement par récurrence.
1. Initialisation 2. Hérédité 3. Conclusion
A. On démontre que si la propriété est vraie pour un entier $n$ quelconque, alors elle est vraie pour l'entier $n+1$. B. On vérifie que la propriété est vraie pour le premier rang $n_0$. C. On affirme que la propriété est vraie pour tout entier $n\geq n_0$.
Corrigé
1-B: L'initialisation consiste à vérifier que la propriété est vraie pour le premier rang $n_0$. 2-A: L'hérédité consiste à démontrer que si la propriété est vraie pour un entier $n$ quelconque, alors elle est vraie pour l'entier $n+1$. 3-C: La conclusion affirme que la propriété est vraie pour tout entier $n\geq n_0$.
Ah, voilà, ça te revient: la récurrence c'est cette histoire en trois étapes. Sauf que cette fois on ne survole pas, on reprend le cours proprement avec la méthode de rédaction, et on applique sur des exercices simples (toujours avec des trous, t'inquiète).
Le B.A.-BA en trois étapes, version rédigée
Pour démontrer par récurrence qu'une propriété $P(n)$ est vraie pour tout entier $n\geq n_0$, on suit TOUJOURS ce plan:
Initialisation: on vérifie $P(n_0)$. On remplace $n$ par $n_0$ dans $P(n)$, on calcule, on conclut: «$P(n_0)$ est vraie».
Hérédité: on fixe un entier $n\geq n_0$ quelconque. On énonce clairement l'hypothèse de récurrence: «On suppose $P(n)$ vraie.» Puis, en utilisant cette hypothèse, on démontre que $P(n+1)$ est vraie. On conclut: «Donc $P(n+1)$ est vraie.»
Conclusion: on dit: «$P(n_0)$ est vraie, et pour tout $n\geq n_0$, $P(n)\Rightarrow P(n+1)$ est vraie. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq n_0$.»
L'erreur classique est d'oublier l'hypothèse de récurrence ou de ne pas s'en servir. Si tu ne l'utilises pas, ta démonstration d'hérédité est fausse.
Exemple modèle: somme géométrique
On va détailler la rédaction sur une somme de puissances de 2.
Propriété: pour tout $n\in\mathbb{N}$, $\sum_{k=0}^{n}2^k = 2^{n+1}-1$.
On pose $P(n)$: $\sum_{k=0}^{n}2^k = 2^{n+1}-1$.
Initialisation ($n=0$): $\sum_{k=0}^{0}2^k = 2^0=1$ et $2^{1}-1=1$. Donc $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$ quelconque. Supposons $P(n)$ vraie, c'est-à-dire $\sum_{k=0}^{n}2^k = 2^{n+1}-1$ (hypothèse de récurrence). Montrons $P(n+1)$, c'est-à-dire $\sum_{k=0}^{n+1}2^k = 2^{n+2}-1$. On a $\sum_{k=0}^{n+1}2^k = \sum_{k=0}^{n}2^k + 2^{n+1}$. Par hypothèse de récurrence, $\sum_{k=0}^{n}2^k = 2^{n+1}-1$, donc $\sum_{k=0}^{n+1}2^k = 2^{n+1}-1 + 2^{n+1} = 2\times 2^{n+1}-1 = 2^{n+2}-1$. Donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n$, donc par récurrence, $P(n)$ vraie pour tout $n\in\mathbb{N}$.
À toi de jouer
1. On veut démontrer par récurrence que pour tout $n\geq 1$, $1+2+3+\dots+n = \frac{n(n+1)}{2}$.
On pose $P(n):\;\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
Initialisation ($n=1$): $\sum_{k=1}^{1} k = \underline{\hspace{1.1em}}$ $\frac{1\times(\underline{\hspace{1.1em}})}{2} = \frac{\underline{\hspace{1.1em}}}{2} = \underline{\hspace{1.1em}}$ Les deux membres sont égaux, donc $P(1)$ est vraie.
Hérédité: Soit $n\geq 1$. On suppose $P(n)$ vraie, c'est-à-dire $\underline{\hspace{1.1em}}$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$. $\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + \underline{\hspace{1.1em}} = \frac{n(n+1)}{2} + \underline{\hspace{1.1em}}$ (par hypothèse de récurrence). $= \frac{n(n+1) + 2\times\underline{\hspace{1.1em}}}{2} = \frac{n^2+n+2n+2}{2} = \frac{n^2+3n+2}{2}$. Or $(n+1)(n+2) = n^2+3n+2$, donc $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$, c'est-à-dire $P(n+1)$ est vraie.
Conclusion: $P(1)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n\geq 1$. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq 1$.
Corrigé
On pose $P(n):\;\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
Initialisation ($n=1$): $\sum_{k=1}^{1} k = 1$ $\frac{1\times(2)}{2} = \frac{2}{2} = 1$ Les deux membres sont égaux, donc $P(1)$ est vraie.
Hérédité: Soit $n\geq 1$. On suppose $P(n)$ vraie, c'est-à-dire $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$. $\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n+1) = \frac{n(n+1)}{2} + (n+1)$ (par hypothèse de récurrence). $= \frac{n(n+1) + 2\times (n+1)}{2} = \frac{n^2+n+2n+2}{2} = \frac{n^2+3n+2}{2}$. Or $(n+1)(n+2) = n^2+3n+2$, donc $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$, c'est-à-dire $P(n+1)$ est vraie.
Conclusion: $P(1)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n\geq 1$. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq 1$.
2. On veut démontrer par récurrence que pour tout $n\in\mathbb{N}$, $4^n - 1$ est divisible par 3.
On pose $P(n):\; 3 \text{ divise } 4^n - 1$ (c'est-à-dire $4^n-1 = 3k$ pour un certain entier $k$).
Initialisation ($n=0$): $4^0 - 1 = \underline{\hspace{1.1em}} - 1 = \underline{\hspace{1.1em}} = 3\times\underline{\hspace{1.1em}}$. Donc 3 divise $4^0-1$, et $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. On suppose $P(n)$ vraie, c'est-à-dire $\underline{\hspace{1.1em}} = 3k$ avec $k\in\mathbb{Z}$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire $4^{n+1}-1$ est divisible par 3. $4^{n+1}-1 = 4\times 4^n - 1 = 4\times(\underline{\hspace{1.1em}} + 1) - 1$ (car $4^n = (4^n-1)+1 = 3k+1$). $= 4\times(3k+1) - 1 = \underline{\hspace{1.1em}}\,k + 4 - 1 = \underline{\hspace{1.1em}}\,k + \underline{\hspace{1.1em}} = 3(\underline{\hspace{1.1em}})$. Comme $4k+1\in\mathbb{Z}$, $4^{n+1}-1$ est un multiple de 3, donc $P(n+1)$ est vraie.
Conclusion: [À compléter]
Corrigé
On pose $P(n):\; 3 \text{ divise } 4^n - 1$ (c'est-à-dire $4^n-1 = 3k$ pour un certain entier $k$).
Initialisation ($n=0$): $4^0 - 1 = 1 - 1 = 0 = 3\times 0$. Donc 3 divise $4^0-1$, et $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. On suppose $P(n)$ vraie, c'est-à-dire $4^n - 1 = 3k$ avec $k\in\mathbb{Z}$ (hypothèse de récurrence). On veut montrer $P(n+1)$, c'est-à-dire $4^{n+1}-1$ est divisible par 3. $4^{n+1}-1 = 4\times 4^n - 1 = 4\times(3k + 1) - 1$ (car $4^n = (4^n-1)+1 = 3k+1$). $= 4\times(3k+1) - 1 = 12k + 4 - 1 = 12k + 3 = 3(4k+1)$. Comme $4k+1\in\mathbb{Z}$, $4^{n+1}-1$ est un multiple de 3, donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ est vraie, et pour tout $n$, $P(n)\Rightarrow P(n+1)$ est vraie. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\in\mathbb{N}$, donc $4^n-1$ est divisible par 3 pour tout $n\in\mathbb{N}$.
3. On considère la suite $(u_n)$ définie par $u_0=5$ et $u_{n+1}=2u_n-1$ pour tout $n\in\mathbb{N}$.
On veut démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n = 2^{n+2}+1$.
Initialisation ($n=0$): $u_0 = \underline{\hspace{1.1em}}$ (par définition). Et $2^{0+2}+1 = 2^{\underline{\hspace{1.1em}}}+1 = \underline{\hspace{1.1em}}+1 = \underline{\hspace{1.1em}}$. On a bien $u_0 = 5$, donc $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. On suppose $P(n)$ vraie, c'est-à-dire: $u_n = \underline{\hspace{1.1em}}$ (hypothèse de récurrence). On veut montrer $P(n+1)$: $u_{n+1} = 2^{(n+1)+2}+1 = 2^{\underline{\hspace{1.1em}}}+1$. Par définition de la suite: $u_{n+1} = 2u_n - 1$. On utilise l'hypothèse de récurrence: $u_{n+1} = 2\times(\underline{\hspace{1.1em}}) - 1 = \underline{\hspace{1.1em}} - 1 = \underline{\hspace{1.1em}}$. Or $2^{n+3}+1 = \underline{\hspace{1.1em}}$, donc $u_{n+1} = 2^{n+3}+1$, c'est-à-dire $P(n+1)$ est vraie.
Conclusion: $P(0)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n$. Par récurrence, $P(n)$ vraie pour tout $n\in\mathbb{N}$.
Corrigé
On considère la suite $(u_n)$ définie par $u_0=5$ et $u_{n+1}=2u_n-1$ pour tout $n\in\mathbb{N}$.
On veut démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n = 2^{n+2}+1$.
Initialisation ($n=0$): $u_0 = 5$ (par définition). Et $2^{0+2}+1 = 2^{2}+1 = 4+1 = 5$. On a bien $u_0 = 5$, donc $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. On suppose $P(n)$ vraie, c'est-à-dire: $u_n = 2^{n+2}+1$ (hypothèse de récurrence). On veut montrer $P(n+1)$: $u_{n+1} = 2^{(n+1)+2}+1 = 2^{n+3}+1$. Par définition de la suite: $u_{n+1} = 2u_n - 1$. On utilise l'hypothèse de récurrence: $u_{n+1} = 2\times(2^{n+2}+1) - 1 = 2\times 2^{n+2}+2 - 1 = 2^{n+3}+1$. Donc $u_{n+1} = 2^{n+3}+1$, c'est-à-dire $P(n+1)$ est vraie.
Conclusion: $P(0)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n$. Par récurrence, $P(n)$ vraie pour tout $n\in\mathbb{N}$.
Là, c'est de la mécanique pure. Cinq mini-exercices quasi identiques. Juste pour que tu intègres le geste. Tu vas enchaîner cinq preuves par récurrence de suites définies par récurrence (sans jeu de mots). Même structure, juste les nombres qui changent. Du confort.
À toi de jouer
1. Soit $(u_n)$ la suite définie par $u_0=1$ et pour tout $n\in\mathbb{N}$, $u_{n+1}=3u_n+2$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n = 2\times 3^n - 1$.
À toi de rédiger les trois étapes (tu peux reprendre le modèle des exercices précédents).
Corrigé
On pose $P(n): u_n = 2\times 3^n - 1$.
Initialisation ($n=0$): $u_0=1$ et $2\times 3^0 - 1 = 2 - 1 = 1$. Donc $P(0)$ est vraie.
Hérédité : Supposons $P(n)$ vraie pour un certain $n \in \mathbb{N}$, c'est-à-dire $w_n = 5^n + 1$. Calculons $w_{n+1}$ à partir de la relation de récurrence :
Or $P(n+1)$ exige $w_{n+1} = 5^{n+1} + 1$. On obtient $5^{n+1} - 3 eq 5^{n+1} + 1$ : l'hérédité est en défaut, et la démonstration ne peut pas être menée à terme.
Vérification directe : $w_1 = 5 \times 2 - 8 = 2$, alors que $5^1 + 1 = 6$. La formule $w_n = 5^n + 1$ est donc fausse dès le rang $1$ avec la relation $w_{n+1} = 5w_n - 8$.
Remarque : l'énoncé contient vraisemblablement une coquille. Si la relation de récurrence est $w_{n+1} = 5w_n - 4$, l'hérédité se conclut correctement : $w_{n+1} = 5(5^n + 1) - 4 = 5^{n+1} + 5 - 4 = 5^{n+1} + 1$, ce qui est bien $P(n+1)$. Sous réserve de cette correction, on conclut par le principe de récurrence que $w_n = 5^n + 1$ pour tout $n \in \mathbb{N}$.
4. Soit $(a_n)$ la suite définie par $a_0=0$ et pour tout $n\in\mathbb{N}$, $a_{n+1}=4a_n+3$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $a_n = 4^n - 1$.
Conclusion: par récurrence, $a_n = 4^n - 1$ pour tout $n$.
5. Soit $(b_n)$ la suite définie par $b_0=7$ et pour tout $n\in\mathbb{N}$, $b_{n+1}=6b_n-35$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $b_n = 2\times 6^n + 5$.
Corrigé
Remarque préalable : La relation $b_{n+1} = 6b_n - 35$ telle qu'elle figure dans l'énoncé ne permet pas d'établir la propriété $b_n = 2\times 6^n + 5$ : l'étape d'hérédité donnerait $6(2\times 6^n+5)-35 = 2\times 6^{n+1}+30-35 = 2\times 6^{n+1}-5$, ce qui contredit la propriété à démontrer. L'énoncé contient vraisemblablement une coquille : la relation correcte est $b_{n+1} = 6b_n - 25$. La démonstration ci-dessous repose sur cette relation.
On pose $P(n) : b_n = 2\times 6^n + 5$.
Initialisation ($n=0$) : $b_0 = 7$ et $2\times 6^0 + 5 = 2\times 1 + 5 = 7$. Donc $P(0)$ est vraie.
Hérédité : Soit $n\in\mathbb{N}$. Supposons que $P(n)$ est vraie, c'est-à-dire $b_n = 2\times 6^n + 5$. Alors : $b_{n+1} = 6b_n - 25 = 6(2\times 6^n + 5) - 25 = 2\times 6^{n+1} + 30 - 25 = 2\times 6^{n+1} + 5$. Donc $P(n+1)$ est vraie.
Conclusion : $P(0)$ est vraie et, pour tout $n\in\mathbb{N}$, $P(n)\Rightarrow P(n+1)$. Par le principe de récurrence, pour tout $n\in\mathbb{N}$, $b_n = 2\times 6^n + 5$.
Cette fois, on monte le niveau de rédaction. Tu vas affronter des énoncés type contrôle: inégalité, divisibilité, suite bornée. Il faut rédiger proprement, sans trous cette fois, comme au DS. Tu te sens prêt? Alors c'est parti.
À toi de jouer
1. Démontrer par récurrence que pour tout entier $n \geq 1$, $3^n \geq 2n + 1$.
Corrigé
On pose $P(n): 3^n \geq 2n+1$. Initialisation ($n=1$): $3^1=3$, $2\times 1+1=3$, donc $3\geq 3$. $P(1)$ vraie. Hérédité: Soit $n\geq 1$. Supposons $3^n \geq 2n+1$. Montrons $3^{n+1} \geq 2(n+1)+1 = 2n+3$. $3^{n+1} = 3 \times 3^n \geq 3(2n+1) = 6n+3$. Or $6n+3 - (2n+3) = 4n \geq 0$ car $n \geq 1$. Donc $6n+3 \geq 2n+3$. Ainsi $3^{n+1} \geq 2n+3$, ce qui prouve $P(n+1)$. Conclusion: $P(1)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n\geq 1$. Par récurrence, $3^n \geq 2n+1$ pour tout $n \geq 1$.
2. Démontrer par récurrence que pour tout $n \in \mathbb{N}$, $5^{2n} - 1$ est divisible par 8.
Corrigé
On pose $P(n): 8 \mid 5^{2n}-1$ (c'est-à-dire $5^{2n}-1 = 8k$ pour un certain $k\in\mathbb{Z}$). Initialisation ($n=0$): $5^{0}-1 = 0 = 8\times 0$, donc $P(0)$ vraie. Hérédité: Soit $n\in\mathbb{N}$. Supposons $5^{2n}-1 = 8k$, avec $k\in\mathbb{Z}$. Montrons que $5^{2(n+1)}-1$ est divisible par 8. $5^{2(n+1)}-1 = 5^{2n+2} - 1 = 25 \times 5^{2n} - 1$. On écrit $25\times 5^{2n} = 25(8k+1) = 25\times 8k + 25$. Donc $5^{2n+2}-1 = 200k + 25 - 1 = 200k + 24 = 8(25k + 3)$. Comme $25k+3\in\mathbb{Z}$, $5^{2n+2}-1$ est multiple de 8. Donc $P(n+1)$ vraie. Conclusion: $P(0)$ vraie, hérédité vérifiée, donc pour tout $n\in\mathbb{N}$, $5^{2n}-1$ est divisible par 8.
3. Soit $(u_n)$ la suite définie par $u_0 = 5$ et pour tout $n\in\mathbb{N}$, $u_{n+1} = \frac{2}{3}u_n + 1$. Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n$ est un nombre rationnel positif. (Indication: on pourra prouver que $0 < u_n \leq 5$.)
Corrigé
On va prouver par récurrence que $0 < u_n \leq 5$ pour tout $n$. Initialisation ($n=0$): $u_0=5$, donc $0<5\leq 5$. Vrai. Hérédité: Supposons $0 < u_n \leq 5$ pour un certain $n$. Montrons $0 < u_{n+1} \leq 5$. $u_{n+1} = \frac{2}{3}u_n + 1$. Comme $u_n > 0$, $\frac{2}{3}u_n > 0$, donc $u_{n+1} > 1$, et en particulier $u_{n+1} > 0$. D'autre part, $u_n \leq 5$, donc $\frac{2}{3}u_n \leq \frac{10}{3}$, d'où $u_{n+1} \leq \frac{10}{3} + 1 = \frac{13}{3} \approx 4,33 \leq 5$. Donc $u_{n+1} \leq 5$. Ainsi $0 < u_{n+1} \leq 5$. La propriété est héréditaire. Conclusion: Pour tout $n$, $0 < u_n \leq 5$, donc chaque $u_n$ est un rationnel positif (car somme et produit de rationnels).
4. On considère la suite $(v_n)$ définie par $v_0=1$ et $v_{n+1} = \sqrt{3v_n + 1}$ pour tout $n\in\mathbb{N}$. Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $1 \leq v_n \leq 2$.
Corrigé
On pose $P(n) : 1 \leq v_n \leq 2$.
Initialisation ($n=0$) : $v_0 = 1$, donc $1 \leq 1 \leq 2$ : $P(0)$ est vraie.
Tentative d'hérédité : Supposons $1 \leq v_n \leq 2$. On cherche à montrer $1 \leq v_{n+1} \leq 2$, avec $v_{n+1} = \sqrt{3v_n + 1}$.
Ce n'est pas un simple défaut de méthode : la propriété est effectivement fausse dès $n = 2$. On calcule $v_1 = \sqrt{3 \times 1 + 1} = \sqrt{4} = 2$, puis $v_2 = \sqrt{3 \times 2 + 1} = \sqrt{7} > 2$. L'encadrement $1 \leq v_n \leq 2$ ne tient donc pas pour $n = 2$.
Conclusion : L'énoncé tel qu'il est posé est incorrect : la suite $(v_n)$ définie par $v_0 = 1$ et $v_{n+1} = \sqrt{3v_n + 1}$ n'est pas bornée supérieurement par $2$. La démonstration demandée ne peut pas être menée à bien.
5. Soit la suite $(u_n)$ définie par $u_0=0$ et $u_{n+1} = 3u_n + 2n + 1$ pour $n\in\mathbb{N}$. Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n = 3^n - n - 1$.
Corrigé
On pose $P(n): u_n = 3^n - n - 1$. Initialisation ($n=0$): $u_0=0$, $3^0 - 0 - 1 = 0$. $P(0)$ vraie. Hérédité: Soit $n\in\mathbb{N}$. Supposons $u_n = 3^n - n - 1$. Alors $u_{n+1} = 3u_n + 2n + 1 = 3(3^n - n - 1) + 2n + 1 = 3^{n+1} - 3n - 3 + 2n + 1 = 3^{n+1} - n - 2$. Or on veut $3^{n+1} - (n+1) - 1 = 3^{n+1} - n - 2$. Donc c'est exact. Conclusion: $P(0)$ vraie, hérédité prouvée, donc $P(n)$ vraie pour tout $n$.
Curieux de voir ce qui t'attend après le bac? La récurrence est partout dans le supérieur: récurrence double, forte, sur des sommes, des intégrales... On va juste soulever un coin du voile avec deux exos plus corsés. Pas de panique, ce n'est pas exigible au bac, mais si tu veux briller ou préparer le supérieur, c'est ici.
Récurrence forte: le principe
Dans une récurrence forte, au lieu de supposer $P(n)$ vraie pour prouver $P(n+1)$, on suppose que $P(0), P(1), \dots, P(n)$ sont toutes vraies. Pratique quand $u_{n+1}$ dépend de plusieurs rangs précédents, comme dans la suite de Fibonacci.
À toi de jouer
1. On définit la suite $(F_n)$ par $F_0=0$, $F_1=1$ et pour tout $n\in\mathbb{N}$, $F_{n+2} = F_{n+1} + F_n$ (suite de Fibonacci). Démontrer par récurrence forte que pour tout $n\geq 1$, $F_n \geq n-1$.
Corrigé
On pose $P(n): F_n \geq n-1$ pour $n\geq 1$. Initialisation: $P(1): F_1=1 \geq 0$, vrai. $P(2): F_2 = F_1+F_0 = 1$, et $2-1=1$, donc $1\geq 1$, vrai. Hérédité (forte): Soit $n\geq 2$. Supposons que pour tout $k$ tel que $1\leq k \leq n$, $P(k)$ est vraie. Montrons $P(n+1)$, c'est-à-dire $F_{n+1} \geq n$. $F_{n+1} = F_n + F_{n-1}$. Par hypothèse de récurrence forte, $P(n)$ donne $F_n \geq n-1$, et $P(n-1)$ donne $F_{n-1} \geq n-2$. Donc $F_{n+1} \geq (n-1) + (n-2) = 2n-3$. On veut $F_{n+1} \geq n$. C'est vrai si $2n-3 \geq n$, c'est-à-dire $n \geq 3$. Pour $n=2$, on a déjà vérifié $P(3)$? Vérifions: $P(3)$: $F_3=2$, $3-1=2$, ok. Donc on peut conclure. Pour $n\geq 3$, $2n-3 \geq n$, donc $F_{n+1} \geq n$, soit $P(n+1)$ vraie. Conclusion: Par récurrence forte, $P(n)$ est vraie pour tout $n\geq 1$. Remarque: l'initialisation multiple (P(1) et P(2)) est typique de la récurrence forte.
2. On souhaite démontrer que pour tout $n\geq 5$, $2^n > n^2$. Une récurrence simple ne semble pas suffire car l'écart se creuse lentement au début. On va utiliser une récurrence «en avant» après avoir vérifié le cas $n=5$.
Démontrer par récurrence cette inégalité. Indication: pour l'hérédité, on pourra utiliser le fait que pour $n\geq 5$, $n^2 \geq 3n$ (à justifier).
Corrigé
On pose $P(n): 2^n > n^2$, pour $n\geq 5$. Initialisation ($n=5$): $2^5 = 32$, $5^2=25$, donc $32>25$. $P(5)$ vraie. Hérédité: Soit $n\geq 5$. Supposons $2^n > n^2$. Montrons $2^{n+1} > (n+1)^2 = n^2+2n+1$. $2^{n+1} = 2\cdot 2^n > 2n^2$ par hypothèse de récurrence. On veut $2n^2 \geq n^2+2n+1$, soit $n^2 \geq 2n+1$. Or pour $n \geq 5$, $n^2 \geq 3n$ (car $n(n-3)\geq 0$), et $3n \geq 2n+1$ pour $n\geq 1$. Donc $n^2 \geq 2n+1$ est vrai. Ainsi $2^{n+1} > 2n^2 \geq n^2+2n+1 = (n+1)^2$, donc $2^{n+1} > (n+1)^2$. $P(n+1)$ est vraie. Conclusion: Par récurrence, pour tout entier $n\geq 5$, $2^n > n^2$.
3. Soit $(u_n)$ la suite définie par $u_0=1$ et $u_{n+1} = 1 + \frac{1}{u_n}$ pour $n\in\mathbb{N}$. Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $1 \leq u_n \leq 2$.
Corrigé
On pose $P(n): 1 \leq u_n \leq 2$. Initialisation ($n=0$): $u_0=1$, donc $1\leq 1\leq 2$. Vrai. Hérédité: Supposons $1\leq u_n \leq 2$. Alors $\frac{1}{2} \leq \frac{1}{u_n} \leq 1$. Donc $1+\frac{1}{2} \leq 1+\frac{1}{u_n} \leq 2$, soit $\frac{3}{2} \leq u_{n+1} \leq 2$. En particulier, $1\leq u_{n+1} \leq 2$. $P(n+1)$ vraie. Conclusion: Par récurrence, pour tout $n$, $u_n$ est compris entre 1 et 2. Cet encadrement permet par exemple d'étudier la convergence de la suite (notion du supérieur).
Fiche gratuite créée par Vidyalaya, association d'éducation populaire — soutien scolaire, FLE & DELF, libre et gratuit pour tous. Tu bloques encore ? Écris-nous, on t'aide gratuitement : contact@vidyalaya.fr.
Fiche librement réutilisable sous licence CC BY-SA 4.0 — copiez, imprimez, adaptez, en citant Vidyalaya et en conservant la même licence.