Fiche d'exercices Logimaths | Terminale spécialité
Fiche d'exercices : Raisonnement par récurrence
9 exercices progressifs ⭐ → ⭐⭐⭐ : cherche d'abord, la correction est sous chaque énoncé
Échauffement
Exercice 1 : Les trois blocs dans l'ordre⭐
On veut démontrer par récurrence que 4^n \geq 3n + 1 pour tout entier naturel n. Remets les phrases dans l'ordre et nomme chaque bloc :
- « La propriété est donc vraie pour tout entier naturel n. »
- « 4^0 = 1 et 3 \times 0 + 1 = 1 : vraie au rang 0. »
- « Supposons 4^k \geq 3k + 1 pour un entier k fixé, et montrons l'inégalité au rang k + 1. »
👆 ▶ Correction de l'exercice 1
Ordre : 2 (initialisation) → 3 (hérédité : hypothèse puis démonstration) → 1 (conclusion).
Les trois blocs sont non négociables : le correcteur les cherche un par un.
Les trois blocs sont non négociables : le correcteur les cherche un par un.
Exercice 2 : Vérifier des initialisations⭐
- Pour « 2^n \geq n + 1 » au rang 0.
- Pour « u_n = 3n - 2 où u_{n+1} = u_n + 3, u_1 = 1 » au rang 1.
- Pour « 7^n - 1 est divisible par 6 » au rang 0.
👆 ▶ Correction de l'exercice 2
1. 2^0 = 1 et 0 + 1 = 1 : 1 ≥ 1 ✔.
2. \begin{aligned}3 \times 1 - 2 &= 1 \\ &= u_1\end{aligned} ✔
3. \begin{aligned}7^0 - 1 &= 0 \\ &= 6 \times 0\end{aligned} Divisible par 6 ✔ (zéro est divisible par tout le monde !).
2. \begin{aligned}3 \times 1 - 2 &= 1 \\ &= u_1\end{aligned} ✔
3. \begin{aligned}7^0 - 1 &= 0 \\ &= 6 \times 0\end{aligned} Divisible par 6 ✔ (zéro est divisible par tout le monde !).
Le cœur du chapitre
Exercice 3 : Expression explicite⭐⭐
La suite (u_n) est définie par u_0 = 3 et u_{n+1} = u_n + 2n + 5.
Démontrer par récurrence que pour tout entier naturel n : {u_n = n^2 + 4n + 3}.
Démontrer par récurrence que pour tout entier naturel n : {u_n = n^2 + 4n + 3}.
👆 ▶ Correction de l'exercice 3
Initialisation (n = 0)\begin{aligned}0^2 + 4 \times 0 + 3 &= 3 \\ &= u_0\end{aligned} ✔
HéréditéSupposons u_k = k^2 + 4k + 3 pour un entier k fixé. Alors :
\begin{aligned}u_{k+1} &= u_k + 2k + 5 \\ &= k^2 + 4k + 3 + 2k + 5 \\ &= k^2 + 6k + 8\end{aligned}
Or \begin{aligned}(k+1)^2 + 4(k+1) + 3 &= k^2 + 2k + 1 + 4k + 4 + 3 \\ &= k^2 + 6k + 8\end{aligned} ✔
ConclusionVraie au rang 0 et héréditaire : {u_n = n^2 + 4n + 3} pour tout n. ∎
HéréditéSupposons u_k = k^2 + 4k + 3 pour un entier k fixé. Alors :
\begin{aligned}u_{k+1} &= u_k + 2k + 5 \\ &= k^2 + 4k + 3 + 2k + 5 \\ &= k^2 + 6k + 8\end{aligned}
Or \begin{aligned}(k+1)^2 + 4(k+1) + 3 &= k^2 + 2k + 1 + 4k + 4 + 3 \\ &= k^2 + 6k + 8\end{aligned} ✔
ConclusionVraie au rang 0 et héréditaire : {u_n = n^2 + 4n + 3} pour tout n. ∎
Exercice 4 : Monotonie par récurrence⭐⭐
La suite (u_n) est définie par u_0 = 1 et u_{n+1} = \tfrac{1}{2}u_n + 3.
Démontrer par récurrence que (u_n) est croissante.
Démontrer par récurrence que (u_n) est croissante.
👆 ▶ Correction de l'exercice 4
On démontre : u_{n+1} \geq u_n pour tout n.
Initialisation\begin{aligned}u_1 &= \tfrac{1}{2} \times 1 + 3 \\ &= 3{,}5 \\ &\geq 1 \\ &= u_0\end{aligned} ✔
HéréditéSupposons u_{k+1} \geq u_k. En divisant par 2 (positif) puis en ajoutant 3 :
\tfrac{1}{2}u_{k+1} + 3 \geq \tfrac{1}{2}u_k + 3, c'est-à-dire {u_{k+2} \geq u_{k+1}} ✔.
ConclusionLa suite est croissante. ∎
Initialisation\begin{aligned}u_1 &= \tfrac{1}{2} \times 1 + 3 \\ &= 3{,}5 \\ &\geq 1 \\ &= u_0\end{aligned} ✔
HéréditéSupposons u_{k+1} \geq u_k. En divisant par 2 (positif) puis en ajoutant 3 :
\tfrac{1}{2}u_{k+1} + 3 \geq \tfrac{1}{2}u_k + 3, c'est-à-dire {u_{k+2} \geq u_{k+1}} ✔.
ConclusionLa suite est croissante. ∎
Exercice 5 : Majoration⭐⭐
Toujours avec u_0 = 1 et u_{n+1} = \tfrac{1}{2}u_n + 3 :
démontrer par récurrence que u_n \leq 6 pour tout entier naturel n. Que peut-on alors dire de la suite ? (Avec l'exercice 4…)
démontrer par récurrence que u_n \leq 6 pour tout entier naturel n. Que peut-on alors dire de la suite ? (Avec l'exercice 4…)
👆 ▶ Correction de l'exercice 5
Initialisation\begin{aligned}u_0 &= 1 \\ &\leq 6\end{aligned} ✔
HéréditéSi u_k \leq 6, alors \begin{aligned}u_{k+1} &= \tfrac{1}{2}u_k + 3 \\ &\leq \tfrac{1}{2} \times 6 + 3 \\ &= 6\end{aligned} ✔
Conclusion et bilanLa suite est croissante (ex. 4) ET majorée par 6 : d'après le théorème de convergence monotone, elle converge (vers 6, comme le confirmera le chapitre des limites).
HéréditéSi u_k \leq 6, alors \begin{aligned}u_{k+1} &= \tfrac{1}{2}u_k + 3 \\ &\leq \tfrac{1}{2} \times 6 + 3 \\ &= 6\end{aligned} ✔
Conclusion et bilanLa suite est croissante (ex. 4) ET majorée par 6 : d'après le théorème de convergence monotone, elle converge (vers 6, comme le confirmera le chapitre des limites).
Exercice 6 : Divisibilité⭐⭐
Démontrer par récurrence que pour tout entier naturel n, 4^n - 1 est divisible par 3.
👆 ▶ Correction de l'exercice 6
Initialisation\begin{aligned}4^0 - 1 &= 0 \\ &= 3 \times 0\end{aligned} ✔
HéréditéSupposons 4^k - 1 = 3p avec p entier. Alors :
\begin{aligned}4^{k+1} - 1 &= 4 \times 4^k - 1 \\ &= 4(3p + 1) - 1 \\ &= 12p + 3 \\ &= 3(4p + 1)\end{aligned}
avec 4p + 1 entier : divisible par 3 ✔.
ConclusionPour tout n, 4^n - 1 est divisible par 3. ∎
HéréditéSupposons 4^k - 1 = 3p avec p entier. Alors :
\begin{aligned}4^{k+1} - 1 &= 4 \times 4^k - 1 \\ &= 4(3p + 1) - 1 \\ &= 12p + 3 \\ &= 3(4p + 1)\end{aligned}
avec 4p + 1 entier : divisible par 3 ✔.
ConclusionPour tout n, 4^n - 1 est divisible par 3. ∎
Pour aller plus loin
Exercice 7 : Bernoulli et les puissances⭐⭐⭐
- Rappelle l'inégalité de Bernoulli.
- En l'appliquant avec a = 0{,}2, montre que 1{,}2^n \geq 1 + 0{,}2n, puis trouve un entier n tel que 1{,}2^n > 100.
- Qu'en déduit-on sur \lim 1{,}2^n ?
👆 ▶ Correction de l'exercice 7
1. Pour a > 0 et n entier naturel : {(1+a)^n \geq 1 + na}.
2. Avec a = 0,2 : 1{,}2^n \geq 1 + 0{,}2n. Il suffit que 1 + 0,2n > 100, soit n > 495 : n = 496 convient.
3. 1 + 0,2n tend vers +\infty, donc par comparaison \lim 1{,}2^n = +\infty : c'est LA preuve type de q^n \to +\infty pour q > 1.
2. Avec a = 0,2 : 1{,}2^n \geq 1 + 0{,}2n. Il suffit que 1 + 0,2n > 100, soit n > 495 : n = 496 convient.
3. 1 + 0,2n tend vers +\infty, donc par comparaison \lim 1{,}2^n = +\infty : c'est LA preuve type de q^n \to +\infty pour q > 1.
Exercice 8 : La chasse à l'erreur⭐⭐⭐
Un élève « démontre » que tous les entiers sont pairs :
« Supposons que k soit pair pour un certain k, disons k = 2p. Alors k + 2 = 2p + 2 = 2(p + 1) est pair aussi. Donc par récurrence, tous les entiers sont pairs. »
« Supposons que k soit pair pour un certain k, disons k = 2p. Alors k + 2 = 2p + 2 = 2(p + 1) est pair aussi. Donc par récurrence, tous les entiers sont pairs. »
- L'hérédité (de k à k + 2) est-elle correcte ?
- Où est la faille ?
👆 ▶ Correction de l'exercice 8
1. Oui, le calcul est juste : pair + 2 = pair.
2. Deux failles : aucune initialisation n'est donnée, et l'hérédité saute de k à k + 2, donc elle ne peut atteindre que les entiers de même parité que le point de départ. En initialisant à 0, on prouve seulement que les entiers PAIRS sont pairs… ce qui manque un peu d'ambition. Moralité : vérifier l'initialisation ET que l'hérédité relie bien k à k + 1.
2. Deux failles : aucune initialisation n'est donnée, et l'hérédité saute de k à k + 2, donc elle ne peut atteindre que les entiers de même parité que le point de départ. En initialisant à 0, on prouve seulement que les entiers PAIRS sont pairs… ce qui manque un peu d'ambition. Moralité : vérifier l'initialisation ET que l'hérédité relie bien k à k + 1.
Exercice 9 : Suite définie par récurrence⭐⭐
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.
Démontrer par récurrence que pour tout n \in \mathbb{N} : u_n = 1 - 3^n.
👆 ▶ Correction de l'exercice 9
Initialisation (n = 0)u_0 = 0 et \begin{aligned}1 - 3^0 &= 1 - 1 \\ &= 0\end{aligned} donc la propriété est vraie au rang 0.
HéréditéSupposons la propriété vraie au rang k, c'est-à-dire :
u_k = 1 - 3^k (H.R., hypothèse de récurrence)
Démontrons qu'elle est alors vraie au rang k+1, c'est-à-dire :
u_{k+1} = 1 - 3^{k+1}
\begin{aligned} u_{k+1} &= 3u_k - 2 \\ &= 3\left(1 - 3^k\right) - 2 \quad \text{(par H.R.)} \\ &= 3 - 3 \times 3^k - 2 \\ &= 3 - 3^{k+1} - 2 \\ &= 1 - 3^{k+1} \end{aligned}
Donc la propriété est vraie au rang k+1.
ConclusionLa 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}. ∎
HéréditéSupposons la propriété vraie au rang k, c'est-à-dire :
u_k = 1 - 3^k (H.R., hypothèse de récurrence)
Démontrons qu'elle est alors vraie au rang k+1, c'est-à-dire :
u_{k+1} = 1 - 3^{k+1}
\begin{aligned} u_{k+1} &= 3u_k - 2 \\ &= 3\left(1 - 3^k\right) - 2 \quad \text{(par H.R.)} \\ &= 3 - 3 \times 3^k - 2 \\ &= 3 - 3^{k+1} - 2 \\ &= 1 - 3^{k+1} \end{aligned}
Donc la propriété est vraie au rang k+1.
ConclusionLa 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}. ∎