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
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é
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}$.
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é
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$.
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é
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
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é
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$.
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é
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}$.
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 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
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é
Initialisation ($n=0$): $u_0=1$ et $2\times 3^0 - 1 = 2 - 1 = 1$. Donc $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. Supposons $P(n)$ vraie: $u_n = 2\times 3^n - 1$ (hypothèse de récurrence). Montrons $P(n+1)$: $u_{n+1} = 2\times 3^{n+1} - 1$.
$u_{n+1} = 3u_n+2 = 3(2\times 3^n - 1) + 2 = 2\times 3^{n+1} - 3 + 2 = 2\times 3^{n+1} - 1$. Donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ vraie et $P(n)\Rightarrow P(n+1)$ vraie pour tout $n$. Par récurrence, $u_n = 2\times 3^n - 1$ pour tout $n\in\mathbb{N}$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $v_n = 2^n + 3$.
Corrigé
Initialisation ($n=0$): $v_0=4$ et $2^0+3 = 1+3=4$. Donc $P(0)$ est vraie.
Hérédité: Soit $n\in\mathbb{N}$. Supposons $P(n)$ vraie: $v_n = 2^n+3$. Montrons $P(n+1)$: $v_{n+1} = 2^{n+1}+3$.
$v_{n+1} = 2v_n - 3 = 2(2^n+3) - 3 = 2^{n+1}+6 - 3 = 2^{n+1}+3$. Donc $P(n+1)$ est vraie.
Conclusion: $P(0)$ vraie et hérédité établie. Par récurrence, $v_n = 2^n+3$ pour tout $n\in\mathbb{N}$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $w_n = 5^n + 1$.
Corrigé
On pose $P(n) : w_n = 5^n + 1$.
Initialisation ($n = 0$) : $w_0 = 2$ et $5^0 + 1 = 1 + 1 = 2$. $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 :
$w_{n+1} = 5w_n - 4 = 5(5^n + 1) - 4 = 5^{n+1} + 5 - 4 = 5^{n+1} + 1.$
C'est exactement $P(n+1)$. L'hérédité est établie.
Conclusion : $P(0)$ est vraie et, pour tout $n \in \mathbb{N}$, $P(n) \Rightarrow P(n+1)$. Par le principe de récurrence, $w_n = 5^n + 1$ pour tout $n \in \mathbb{N}$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $a_n = 4^n - 1$.
Corrigé
Initialisation ($n=0$): $a_0=0$, $4^0-1=0$. $P(0)$ vraie.
Hérédité: Supposons $a_n = 4^n - 1$. $a_{n+1}=4a_n+3 = 4(4^n-1)+3 = 4^{n+1}-4+3 = 4^{n+1}-1$, donc $P(n+1)$ vraie.
Conclusion: par récurrence, $a_n = 4^n - 1$ pour tout $n$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $b_n = 2\times 6^n + 5$.
Corrigé
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
Corrigé
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$.
Corrigé
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.
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é
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).
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $1 \leq v_n \leq 4$.
Corrigé
On pose $P(n) : 1 \leq v_n \leq 4$.
Initialisation ($n=0$) : $v_0 = 1$, donc $1 \leq 1 \leq 4$ : $P(0)$ est vraie.
Hérédité : Soit $n \in \mathbb{N}$. Supposons $1 \leq v_n \leq 4$. Montrons $1 \leq v_{n+1} \leq 4$, avec $v_{n+1} = \sqrt{3v_n + 1}$.
Minoration : $v_n \geq 1 \Rightarrow 3v_n + 1 \geq 4 \Rightarrow v_{n+1} \geq \sqrt{4} = 2 \geq 1$.
Majoration : $v_n \leq 4 \Rightarrow 3v_n + 1 \leq 13 \Rightarrow v_{n+1} \leq \sqrt{13} \approx 3{,}61 \leq 4$.
Donc $1 \leq v_{n+1} \leq 4$ : $P(n+1)$ est vraie.
Conclusion : $P(0)$ est vraie et l'hérédité est établie. Par le principe de récurrence, $1 \leq v_n \leq 4$ pour tout $n \in \mathbb{N}$. À noter : la borne $4$ n'est pas la plus fine possible, mais c'est elle qui rend l'hérédité concluante — une majoration par $2$ échouerait dès $v_2 = \sqrt{7} > 2$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $u_n = 3^n - n - 1$.
Corrigé
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
Démontrer par récurrence forte que pour tout $n\geq 1$, $F_n \geq n-1$.
Corrigé
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.
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é
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$.
Démontrer par récurrence que pour tout $n\in\mathbb{N}$, $1 \leq u_n \leq 2$.
Corrigé
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).