Dans cet article, nous présentons le principe du raisonnement par récurrence double, accompagné d’une série d’exercices corrigés pour vous aider à assimiler cette notion et à comprendre dans quels cas il est pertinent d’utiliser ce type de récurrence.
1) Principe du raisonnement par récurrence double
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 \), on utilise le raisonnement par récurrence double en suivant les trois étapes suivantes :
- Initialisation : On vérifie que \( P(0) \) et \( P(1) \) sont vraies.
- Hérédité : On fixe \( n \in \mathbb{N} \), puis on suppose que \( P(n) \) et \( P(n+1) \) sont vraies, et on démontre que \( P(n+2) \) est vraie.
Autrement dit, on montre que : \( \forall n \in \mathbb{N},\ P(n) \text{ et } P(n+1) \Rightarrow P(n+2) \) - Conclusion : On conclut que \( \forall n \in \mathbb{N},\ P(n) \).
Lorsque le premier indice est \( n_0 \in \mathbb{N^*} \), on procède comme suit :
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 \), on utilise le raisonnement par récurrence double en suivant les trois étapes suivantes :
- Initialisation : On vérifie que \( P(n_0) \) et \( P(n_0 + 1) \) sont vraies.
- Hérédité : On fixe un entier naturel \( n \geq n_0 \), puis on suppose que \( P(n) \) et \( P(n+1) \) sont vraies, et on démontre que \( P(n+2) \) est vraie.
Autrement dit, on montre que : \( \forall n \geq n_0,\ P(n) \text{ et } P(n+1) \Rightarrow P(n+2) \) - Conclusion : On conclut que \( \forall n \geq n_0,\ P(n) \).
2) Quand utiliser la récurrence double à 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 a donc naturellement tendance à 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 envisager d’utiliser la récurrence double lorsqu’à l’étape de l’hérédité, on est incapable de prouver que \( P(n) \Rightarrow P(n+1) \), mais qu’on est capable de démontrer que \( P(n) \) et \( P(n+1) \Rightarrow P(n+2) \).
Voici un exemple qui illustre l’insuffisance de la récurrence simple et la nécessité d’utiliser la récurrence double.
On définit :
\[
U_0 = 1,\quad U_1 = 2,\quad \text{et} \quad \forall n \in \mathbb{N},\ U_{n+2} = \frac{1}{2} \sqrt{U_{n+1}} + U_n^2
\]
Montrer que \( \forall n \in \mathbb{N},\ U_n \geq 1 \).
Si on tente d’utiliser ici la récurrence simple, on se retrouve bloqué à l’étape de l’hérédité, car il est impossible de montrer que \( U_{n+1} \geq 1 \) en supposant seulement \( U_n \geq 1 \).
En revanche, on voit immédiatement que si \( U_n \geq 1 \) et \( U_{n+1} \geq 1 \), alors :
\[
U_{n+2} = \frac{1}{2} \sqrt{U_{n+1}} + U_n^2 \geq \frac{1}{2} \cdot 1 + 1 = \frac{3}{2} \geq 1
\]
Ce qui justifie l’usage de la récurrence double.
Solution complète :
- Initialisation : (pour \( n = 0 \) et \( n = 1 \)) :
\[
U_0 = 1 \geq 1 \quad \text{et} \quad U_1 = 2 \geq 1
\]
La propriété est donc vraie pour \( n = 0 \) et \( n = 1 \). - Hérédité :
Soit \( n \in \mathbb{N} \). On suppose que \( U_n \geq 1 \) et \( U_{n+1} \geq 1 \).
Alors :
\[
U_{n+2} = \frac{1}{2} \sqrt{U_{n+1}} + U_n^2 \geq \frac{1}{2} \cdot 1 + 1 = \frac{3}{2} \geq 1
\]
Donc \( U_{n+2} \geq 1 \). La propriété est vraie pour \( n+2 \).
- Conclusion : Par le principe de récurrence double, on a démontré que :
\[
\forall n \in \mathbb{N},\ U_n \geq 1
\]
3) Exercice corrigé sur la récurrence double
Exercice 1 ⭐️⭐️
On considère la suite \( \left(u_{n}\right)_{n \in \mathbb{N}} \) définie par :
\( u_{0}=0, u_{1}=1 \) et \( \forall n \in \mathbb{N}, \quad u_{n+2}=\frac{u_{n+1}+u_{n}}{2}+1 \)
Montrer que la suite \( \left(u_{n}\right)_{n \in \mathbb{N}} \) est strictement croissante.
Indications
La suite \( (u_{n} ) \) est strictement croissante si \( \forall n \in \mathbb{N}, \ u_{n} < u_{n+1} \).
Faire une récurrence double.
Corrigé
Montrons que \( \forall n \in \mathbb{N},\ u_n < u_{n+1} \)
- Initialisation :
On a \( u_0 < u_1 \), la propriété est donc vraie pour \( n = 0 \).
On a \( u_2 = \frac{u_1 + u_0}{2} + 1 = \frac{3}{2} \), donc \( u_1 < u_2 \), la propriété est aussi vraie pour \( n = 1 \). - Hérédité :
Soit \( n \in \mathbb{N} \). On suppose que \( u_n < n_{n+1} \) et \( u_{n+1} < u_{n+2} \).
Alors :
\[
\frac{u_{n+1} + u_n}{2} + 1 < \frac{u_{n+2} + u_{n+1}}{2} + 1 \]
Donc : \[ u_{n+2} < u_{n+3}
\]
La propriété est donc vraie pour \( n+2 \).
- Conclusion :
Par le principe de la récurrence double, nous avons prouvé que \( \forall n \in \mathbb{N},\ u_n < u_{n+1} \).
Cela signifie que la suite \( (u_n)_{n \in \mathbb{N}} \) est strictement croissante.
Exercice 2 ⭐️⭐️
On considère la suite \( (U_n)_{n \in \mathbb{N}} \) définie par :
\[
U_0 = 0,\quad U_1 = -3,\quad \forall n \in \mathbb{N},\ U_{n+2} = -U_{n+1} + 2U_n
\]
Montrer que \( \forall n \in \mathbb{N},\ U_n = -1 + (-2)^n \)
Indications
Utiliser une récurrence double.
Corrigé
- Initialisation :
\[
\begin{aligned}
U_0 &= -1 + (-2)^0 = -1 + 1 = 0 \\
U_1 &= -1 + (-2)^1 = -1 – 2 = -3
\end{aligned}
\] - Hérédité :
Soit \( n \in \mathbb{N} \), supposons que \( U_n = -1 + (-2)^n \) et \( U_{n+1} = -1 + (-2)^{n+1} \)
Alors :
\[
\begin{aligned}
U_{n+2} &= -U_{n+1} + 2U_n \\
&= -(-1 + (-2)^{n+1}) + 2(-1 + (-2)^n) \\
&= 1 – (-2)^{n+1} – 2 + 2(-2)^n \\
&= -1 + (-2)^{n+2}
\end{aligned}
\] - Conclusion :
Par récurrence double, \( \forall n \in \mathbb{N},\ U_n = -1 + (-2)^n \)
Exercice 3 ⭐️⭐️⭐️
Soit \( x \in \mathbb{R}^* \) tel que \( x + \frac{1}{x} \in \mathbb{Z} \). Montrer que :
\[
\forall n \in \mathbb{N},\ x^n + \frac{1}{x^n} \in \mathbb{Z}
\]
Indications
Faire une récurrence double.
Corrigé
- Initialisation :
\[
x^0 + \frac{1}{x^0} = 1 + 1 = 2 \in \mathbb{Z}
\]
\[
x^1 + \frac{1}{x^1} = x + \frac{1}{x} \in \mathbb{Z} \quad \text{(par hypothèse)}
\] - Hérédité :
Soit \( n \in \mathbb{N} \), on suppose que \( x^n + \frac{1}{x^n} \in \mathbb{Z} \) et \( x^{n+1} + \frac{1}{x^{n+1}} \in \mathbb{Z} \)
On utilise :
\[
\left(x + \frac{1}{x}\right)\left(x^{n+1} + \frac{1}{x^{n+1}}\right) = x^{n+2} + \frac{1}{x^{n+2}} + x^n + \frac{1}{x^n}
\]
Comme \( x + \frac{1}{x} \in \mathbb{Z} \), \( x^n + \frac{1}{x^n} \in \mathbb{Z} \) et \( x^{n+1} + \frac{1}{x^{n+1}} \in \mathbb{Z} \), alors \( x^{n+2} + \frac{1}{x^{n+2}} \in\mathbb{Z} \). - Conclusion :
Par récurrence double, on a bien :
\[
\forall n \in \mathbb{N},\ x^n + \frac{1}{x^n} \in \mathbb{Z}
\]
Exercice 4 ⭐️⭐️⭐️
Montrer que : \( \forall n \in \mathbb{N},(1+\sqrt{2})^{n}+(1-\sqrt{2})^{n} \in \mathbb{N} \)
Indications
Utiliser une récurrence double.
Corrigé
- Initialisation :
\[
(1+\sqrt{2})^0 + (1-\sqrt{2})^0 = 1 + 1 = 2 \in \mathbb{N}
\]
\[
(1+\sqrt{2})^1 + (1-\sqrt{2})^1 = (1+\sqrt{2}) + (1-\sqrt{2}) = 2 \in \mathbb{N}
\] - Hérédité :
Soit \( n \in \mathbb{N} \). On suppose que \( (1+\sqrt{2})^n + (1-\sqrt{2})^n \in \mathbb{N} \) et \( (1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1} \in \mathbb{N} \)
Alors :
\[
\begin{aligned}
(1+\sqrt{2})^{n+2} + (1-\sqrt{2})^{n+2} &= (1+\sqrt{2})^2 (1+\sqrt{2})^n + (1-\sqrt{2})^2 (1-\sqrt{2})^n \\
&= (3 + 2\sqrt{2})(1+\sqrt{2})^n + (3 – 2\sqrt{2})(1-\sqrt{2})^n \\
&= (1+\sqrt{2})^n + (1-\sqrt{2})^n + 2\left((1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1} \right)
\end{aligned}
\]
Donc \( (1+\sqrt{2})^{n+2} + (1-\sqrt{2})^{n+2} \in \mathbb{N} \)
- Conclusion :
Par récurrence double, \( \forall n \in \mathbb{N},\ (1+\sqrt{2})^n + (1-\sqrt{2})^n \in \mathbb{N} \)