Dans cet article, nous vous présentons le principe du raisonnement par récurrence forte, accompagné d’une série d’exercices corrigés pour vous aider à assimiler cette notion et à savoir dans quelles situations il est pertinent d’utiliser ce type de récurrence.
1) Principe du raisonnement par récurrence forte
Pour démontrer que \(\forall n \in \mathbb{N},\ P(n)\), où \( P(n) \) est une propriété qui dépend de l’entier naturel \(n\), en utilisant le raisonnement par récurrence forte, on suit les trois étapes suivantes :
- Initialisation : On vérifie que \(P(0)\) est vraie.
- Hérédité : On fixe \(n \in \mathbb{N}\), puis on suppose que \(\forall k \in \{0, \ldots, n\},\ P(k)\) est vraie, et on démontre que \(P(n+1)\) est vraie.
Autrement dit, on montre que :
\[
\forall n \in \mathbb{N},\ \left( \forall k \in \{0, \ldots, n\},\ P(k) \right) \Rightarrow P(n+1).
\] - Conclusion : On conclut que \(\forall n \in \mathbb{N},\ P(n)\) est vraie.
Lorsque le premier indice est \(n_{0} \in \mathbb{N}^{*}\), on procède ainsi :
Pour démontrer que \(\forall n \geq n_{0},\ P(n)\), où \( P(n)\) est une propriété qui dépend de l’entier naturel \(n\), en utilisant le raisonnement par récurrence forte, on suit les trois étapes suivantes :
- Initialisation : On vérifie que \(P\left(n_{0}\right)\) est vraie.
- Hérédité : On fixe un entier naturel \(n \geq n_{0}\), puis on suppose que \(\forall k \in \left\{n_{0}, n_{0}+1, \ldots, n\right\},\ P(k)\) est vraie, et on démontre que \(P(n+1)\) est vraie.
Autrement dit, on montre que :
\[
\forall n \geq n_{0},\ \left(\forall k \in \left\{n_{0}, \ldots, n\right\}, P(k)\right) \Rightarrow P(n+1)
\]
- Conclusion : On conclut que \(\forall n \geq n_{0},\ P(n)\) est vraie.
2) Quand utiliser la récurrence forte à la place de la récurrence simple.
Lorsqu’on cherche à démontrer que \(\forall n \geq n_{0},\ P(n)\), où \( P(n)\) est une propriété qui dépend d’un entier naturel \(n\), on pense généralement à utiliser un raisonnement par récurrence.
On doit d’abord penser à utiliser la récurrence simple, qui est le type de récurrence le plus utilisé et qui fonctionne dans la plupart des cas.
Il faut cependant penser à utiliser le raisonnement par récurrence forte lorsque, dans l’étape d’hérédité, on est incapable de prouver \( \forall n \geq n_{0},\ P(n) \Rightarrow P(n+1) \) et que l’on a besoin de \( P\left(n_{0}\right),\ P\left(n_{0}+1\right),\ \ldots,\ P(n)\) pour prouver \(P(n+1)\).
Voici un exemple qui illustre l’insuffisance de la récurrence simple et la nécessité de l’utilisation de la récurrence forte.
On pose : \( \displaystyle U_{0} = 1, \quad \forall n \in \mathbb{N}, \quad U_{n+1} = \sum_{k=0}^{n} \frac{U_{k}}{k+1}\).
Montrer que \(\forall n \in \mathbb{N},\ U_{n} \geq 0\).
Si on tente ici d’utiliser la récurrence simple, on va se bloquer dans l’étape de l’hérédité, car il nous sera impossible de montrer que \(U_{n+1} \geq 0\) en supposant seulement que \(U_{n} \geq 0\) pour un certain \(n\) fixé dans \(\mathbb{N}\).
Par contre, on voit immédiatement que si on a \(\forall k \in \{0, \ldots, n\},\ U_{k} \geq 0\), alors on obtient \(U_{n+1} \geq 0\), d’où la nécessité de recourir à un raisonnement par récurrence forte.
Rédigeons maintenant une bonne solution de cette question :
- Initialisation : pour \(n=0\),
\(U_{0} = 1 \geq 0\). La propriété est alors vraie pour \(n=0\). - Hérédité
Soit \(n \in \mathbb{N}\). On suppose que \(\forall k \in \{0, \ldots, n\},\ U_{k} \geq 0\).
Donc \( \displaystyle \sum_{k=0}^{n} \frac{U_{k}}{k+1} \geq 0\).
Ainsi, \(U_{n+1} \geq 0\).
La propriété est alors vraie pour \(n+1\).
- Conclusion : Par le principe de la récurrence forte, nous avons démontré que \(\forall n \in \mathbb{N},\ U_{n} \geq 0\).
3) Exercice corrigé sur la récurrence forte
Exercice 1 ⭐️⭐️
On considère la suite \( \left(u_{n}\right)_{n \in \mathbb{N}} \) définie par :
\( \displaystyle u_{0}=1 \text { et } \forall n \in \mathbb{N} \quad u_{n+1}=\frac{2}{n+1} \sum_{k=0}^{n} u_{k} u_{n-k} \)
Montrer que : \( \forall n \in \mathbb{N}, \quad u_{n}=2^{n} \)
Corrigé
- Initialisation :
On a \(U_{0} = 1 = 2^{0}\). La propriété est alors vraie pour \(n = 0\). - Hérédité :
Soit \(n \in \mathbb{N}\). On suppose que \(\forall k \in \{0, \ldots, n\},\ U_{k} = 2^{k}\).
\[
\begin{aligned}
U_{n+1} & = \frac{2}{n+1} \sum_{k=0}^{n} U_{k} \, U_{n-k} \\
& = \frac{2}{n+1} \sum_{k=0}^{n} 2^{k} \cdot 2^{\,n-k} \quad (\text{par hypothèse de récurrence}) \\
& = \frac{2}{n+1} \sum_{k=0}^{n} 2^{n} \\
& = \frac{2}{n+1} \cdot (n+1) \cdot 2^{n} \\
U_{n+1} & = 2^{n+1}
\end{aligned}
\]
- Conclusion : Par le principe de la récurrence forte, on conclut que \(\forall n \in \mathbb{N},\ U_{n} = 2^{n}\).
Corrigé en video
Exercice 2 ⭐️⭐️⭐️
Montrer que \( \forall n \in \mathbb{N}^{*}, \exists(p, q) \in \mathbb{N}^{2}, n=2^{p}(2 q+1) \)
Indications
Appliquer une récurrence forte en distinguant les cas \(n\) pair et \(n\) impair.
Corrigé
- Initialisation :
\[
2 = 2^{0} \big( 2 \times 0 + 1 \big)
\]
La propriété est alors vérifiée pour \(n = 1 \quad (p = 0, q = 1)\).
- Hérédité :
Soit \(n \in \mathbb{N}^{*}\). On suppose que \(\forall k \in \{1, \ldots, n\},\ \exists (p, q) \in \mathbb{N}^{2},\ k = 2^{p} (2q + 1)\).
\(\mathbf{1^{\text{er}}\ cas}\) : si \(n+1\) est impair,
alors \(\exists q \in \mathbb{N},\ n+1 = 2q + 1 = 2^{0}(2q + 1)\).
\(\mathbf{2^{\text{ème}}\ cas}\) : si \(n+1\) est pair,
alors \(\exists k \in \{1, \ldots, n\},\ n+1 = 2k\).
Par hypothèse de récurrence, \(\exists (p, q) \in \mathbb{N}^{2},\ k = 2^{p}(2q + 1)\).
Donc \(n+1 = 2^{p+1}(2q + 1)\).
Ainsi, dans les deux cas : \(\exists (p, q) \in \mathbb{N}^{2},\ n+1 = 2^{p}(2q + 1)\).
Conclusion :
Par le principe de la récurrence forte :
\[
\forall n \in \mathbb{N}^{*},\ \exists (p, q) \in \mathbb{N}^{2},\ n = 2^{p}(2q + 1).
\]
Corrigé en vidéo
Exercice 3 ⭐️⭐️⭐️
Montrer que tout entier \( n \geq 2 \) se décompose en produit de nombres premiers.
Indications
Utiliser une récurrence forte. Lors de l’étape d’hérédité, distinguer les cas selon que \( n+1 \) est un nombre premier ou non.
Corrigé
- Initialisation :
La propriété est vérifiée pour \(n = 2\), car \(2\) est premier. - Hérédité :
Soit \(n\) un entier \(\geq 2\).
On suppose que \(\forall k \in \{2, \ldots, n\},\ k\) se décompose en produit de nombres premiers.
\(\underline{\mathbf{1^{\text{er}}\ cas}}\) : si \(n+1\) est premier,
la propriété est vérifiée pour \(n+1\).
\(\underline{\mathbf{2^{\text{ème}}\ cas}}\) : si \(n+1\) n’est pas premier,
alors \(\exists a, b \in \{2, \ldots, n\},\ n+1 = ab\).
Par hypothèse de récurrence, \(a\) et \(b\) se décomposent en produit de nombres premiers, il en est donc de même pour leur produit \(n+1\).
Nous avons ainsi démontré, par disjonction de cas, que \(n+1\) se décompose en produit de nombres premiers.
- Conclusion :
Tout entier \(n \geq 2\) se décompose en produit de nombres premiers.
Corrigé en vidéo
Exercice 4 ⭐️⭐️
On considère la suite \( (u_{n} )_{n \in \mathbb{N} } \) définie par : \( u_{0}=1 \ et \ \forall n \in \mathbb{N}, \ u_{n+1}= \sum_{k=0}^{n} \frac {u_{k}}{k!} \)
Montrer que : \( \forall n \in \mathbb{N}, \ u_{n} \in \mathbb{Q} \)
Indications
Utiliser un raisonnement par la récurrence forte
Corrigé
- Initialisation :
On a \(U_{0} = 1 \in \mathbb{Q}\). - Hérédité :
Soit \(n \in \mathbb{N}\). On suppose que \(\forall k \in \{0, \ldots, n\},\ U_{k} \in \mathbb{Q}\).
Donc \(\displaystyle \sum_{k=0}^{n} \frac{U_{k}}{k!} \in \mathbb{Q}\) (car \(\mathbb{Q}\) est stable par quotient et par somme).
D’où \(U_{n+1} \in \mathbb{Q}\).
- Conclusion :
Par le principe de la récurrence forte, nous avons prouvé que \(\forall n \in \mathbb{N},\ U_{n} \in \mathbb{Q}\).