Cet article s’inscrit dans la continuité de l’article « Révisions d’été – Le raisonnement par récurrence (Partie I) » (Que vous pouvez consulter en cliquant ici). À ce titre, les deux articles sont complémentaires.

I. Le principe de récurrence double :

On rencontre parfois des récurrences un petit peu plus compliquées, où l’on ne sait pas déduire $\mathcal{P}_{n+1}$ de $\mathcal{P}_{n}$ mais seulement $\mathcal{P}_{n+2}$ de $\mathcal{P}_{n}$ ET $\mathcal{P}_{n+1}$.

Une telle récurrence est appelée récurrence double. Parfois, on parle de récurrence à deux termes ou encore récurrence d’ordre deux. Les récurrences « traditionnelles » sont dites simples.

La rédaction doit donc être adaptée, la vérification de l’initialisation doit comporter $\mathcal{P}_{0}$ et $\mathcal{P}_{1}$, et le principe de raisonnement par récurrence prend dans ce cas la forme suivante :

Soit $n$ un entier naturel et $\mathcal{P}_{n}$ une propriété.

Si $\displaystyle\underbrace{\mathcal{P}_0\text{ ET }\mathcal{P}_1 \text{ sont vraies}}_{\text{Initialisation}}\qquad$ et si $\displaystyle\qquad\underbrace{\forall n\in\mathbb{N},\quad\mathcal{P}_n\,\text{ET }\mathcal{P}_{n+1}\,\Longrightarrow\, \mathcal{P}_{n+2}}_{\text{Hérédité}}\,,\qquad$ alors $\forall n\in\mathbb{N},\quad\mathcal{P}_n$.

 

— Exemple 1 —

Suite de Fibonacci :

Soit $n$ un entier naturel non nul.

On considère la suite $\displaystyle (F_n)_{n\geq 1}$ définie par :

$F_1=1\,$, $F_2=2\,$ et $\forall n\in\mathbb{N}^*\,\quad F_{n+2}=F_{n+1}+F_{n}$

Montrer que pour tout entier naturel $n$ non nul, on a $F_n \geq n$.

Correction :

Pour $n$ dans $\mathbb{N}^*$, soit $\mathcal{P}_n$ la propriété :

$$F_n \geq n$$

La définition de $\displaystyle (F_n)_{n\geq 1}$ suggère d’établir $\mathcal{P}_n$ par une récurrence double.

 

Initialisation :

On a $F_1=1\geq 1$ et $F_2=2\geq 2$.

Les propriétés $\mathcal{P}_0$ et $\mathcal{P}_1$ sont donc vérifiées.

 

Hérédité :

Soit $n$ dans $\mathbb{N}^*$ tel que $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ soient vraies.

On a donc,

$F_n \geq n$ et $F_{n+1} \geq n+1$

Comme de par sa définition, on a :

$$F_{n+2}=F_{n+1}+F_{n}$$

Alors,

$$\begin{align}F_{n+2}&\geq n+1+n\\&\geq 2n+1\\&\geq n+2 \quad\text{car }n\geq 1\end{align}$$

La propriété $\mathcal{P}_{n+2}$ est démontrée.

On peut donc conclure que la propriété $\mathcal{P}_{n}$ est vraie pour tout $n\in\mathbb{N}^*$.

C’est à dire que pour tout $n\in\mathbb{N}^*$, on a $F_n \geq n$.

 

— Exemple 2 —

Soit $n$ un entier naturel.

On considère la suite $(u_n)_{n\geq 0}$ définie par :

$u_0=2\,$, $u_1=5\,$ et $\forall n\in\mathbb{N}\,\quad u_{n+2}=5u_{n+1}-6u_{n}$

Montrer que pour tout $n$ dans $\mathbb{N}$, on a :

$$u_n=2^n+3^n$$

Correction :

Pour $n$ dans $\mathbb{N}$, soit $\mathcal{P}_n$ la propriété :

$$u_n=2^n+3^n$$

La définition de $(u_n)_{n\geq 0}$ suggère d’établir $\mathcal{P}_n$ par une récurrence double.

 

Initialisation :

On a $u_0=2=2^0+3^0$ et $u_1=5=2^1+3^1$.

Les propriétés $\mathcal{P}_0$ et $\mathcal{P}_1$ sont donc vérifiées.

 

Hérédité :

Soit $n$ dans $\mathbb{N}$ tel que $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ soient vraies.

On a donc,

$u_n=2^n+3^n$ et $u_{n+1}=2^{n+1}+3^{n+1}$

Par ailleurs,

$$u_{n+2}=5u_{n+1}-6u_n$$

Soit grâce à $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$,

$$\begin{align}u_{n+2}&=5\left(2^{n+1}+3^{n+1}\right)-6\left(2^n+3^n\right)\\&=5\times 2^{n+1}-6\times 2^n+5\times 3^{n+1}-6\times 3^n\\&=5\times 2^{n+1}-3\times 2\times 2^n+5\times 3^{n+1}-2\times 3\times 3^n\\&=5\times 2^{n+1}-3\times 2^{n+1}+5\times 3^{n+1}-2\times 3^{n+1}\\&=2\times 2^{n+1}+3\times 3^{n+1}\\&=2^{n+2}+3^{n+2}\end{align}$$

La prorpriété $\mathcal{P}_{n+2}$ est démontrée.

On peut donc conclure que la propriété $\mathcal{P}_{n}$ est vraie pour tout $n$.

C’est à dire que pour tout $n\in\mathbb{N}$, on a $u_n=2^n+3^n$.

 

— Exemple 3 —

Soit $n$ un entier naturel.

On considère la suite $(u_n)_{n\in\mathbb{N}}$ définie par :

$u_0=1\,$, $u_1=4\,$ et $\forall n\in\mathbb{N}\,,\quad u_{n+2}=\sqrt{u_n u_{n+1}}$

Montrer que pour tout $n$ dans $\mathbb{N}$, $u_n$ est bien défini et $u_n >0$.

 

Correction :

Pour $n$ dans $\mathbb{N}$, soit $\mathcal{P}_n$ la propriété :

$u_n$ est bien défini et $u_n>0$

La définition de $(u_n)_{n\geq 0}$ suggère d’établir $\mathcal{P}_n$ par une récurrence double.

 

Initialisation :

Par définition, on a $u_0=1$ et $u_1=4$.

Donc $u_0$ et $u_1$ sont bien définis et strictement positifs.

$\mathcal{P}_0$ et $\mathcal{P}_1$ sont donc vérifiées.

 

Hérédité :

Soit $n$ dans $\mathbb{N}$ tel que $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ soient vraies.

Par définition de la suite $(u_n)_{n\in\mathbb{N}}$, on a :

$$u_{n+2}=\sqrt{u_n u_{n+1}}$$

Or, grâce à $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$, on sait que $u_n$ et $u_{n+1}$ sont bien définis et strictement positifs. Ainsi, $\displaystyle u_n u_{n+1} >0$

On en déduit que,

$u_{n+2}$ est bien défini et $u_{n+2}>0$.

La propriété $\mathcal{P}_{n+2}$ est démontrée.

On peut donc conclure que la propriété $\mathcal{P}_{n}$ est vraie pour tout $n$.

C’est à dire que pour tout $n\in\mathbb{N}$, $u_n$ est bien défini et on a $u_n>0$.

 

II. Synthèse :

Voici une proposition de rédaction quand on veut montrer une propriété par récurrence double.

On énonce la propriété à démontrer : $\forall n\in\mathbb{n}\,,\quad\mathcal{P}_n$.

Initialisation : On vérifie que $\mathcal{P}_0$ ET $\mathcal{P}_1$ sont vraies.

Hérédité : On fixe $n$ dans $\mathbb{N}$ tel que $\mathcal{P}_n$ ET $\mathcal{P}_{n+1}$ soient vraies et démontre que $\mathcal{P}_{n+2}$ est vraie.

Conclusion.

 

Remarque :

Il existe bien des récurrences triples, quadruples, quintuple, …

Ainsi, pour la récurrence triple, le principe est le suivant :

$$\left(\mathcal{P}_{n}\,\text{ET }\mathcal{P}_{n+1}\,\text{ET }\mathcal{P}_{n+2}\right)\qquad\Longrightarrow\mathcal{P}_{n+3}$$

III. Le principe de récurrence forte :

Dans certaines situations, on ne sait déduire $\mathcal{P}_{n+1}$ que de TOUTES les propriétés précédentes $\mathcal{P}_{0}$, $\mathcal{P}_{1}$, $\mathcal{P}_{2}$, … jusqu’à $\mathcal{P}_{n}$.

Une telle récurrence est appelée récurrence forte. Là aussi, la rédaction doit être adaptée et le principe de raisonnement par récurrence prend dans ce cas la forme suivante :

Soit $n$ un entier naturel et $\mathcal{P}_{n}$ une propriété.

Si $\displaystyle\underbrace{\mathcal{P}_0\text{ est vraie}}_{\text{Initialisation}}\qquad$ et si $\displaystyle\qquad\underbrace{\forall n\in\mathbb{N},\quad(\mathcal{P}_0\text{ et }\mathcal{P}_1\text{ et }\mathcal{P}_2\,\text{ et }\cdots\text{ et }\mathcal{P}_n)\,\Longrightarrow\, \mathcal{P}_{n+1}}_{\text{Hérédité}}\,,\qquad$ alors $\forall n\in\mathbb{N},\quad\mathcal{P}_n$.

 

— Exemple —

 

Décomposition d’un entier en produit de nombres premiers.

Montrer que tout entier naturel $n\geq 2$ est produit de nombres premiers.

Correction :

Intuitivement, on a $2=2\times 1$, $3=3\times 1$, $4=2\times 2$, $5=5\times 1$, $6=2\times 3$, … L’assertion semble être vraie. Démontrons ce résultat à l’aide d’une récurrence forte.

Pour tout entier naturel $n\geq 2$, soit $\mathcal{P}_{n}$ la propriété :

$n$ est produit de nombres premiers

Initialisation :

Puisque $2=2\times 1$, alors $\mathcal{P}_{2}$ est vraie.

 

Hérédité :

Soit $n\geq 2$.

Supposons que $\mathcal{P}_{k}$ est vraie pour tout $k$ de $[2\,,\cdots\,,n]$, c’est à dire que $k={2\,,3\,,4\,,\cdots\,,n}$ et montrons que $n+1$ est produit de nombres premiers.

 

Si l’entier $n+1$ est premier, alors il est le produit de nombres premiers

Sinon, il (l’entier $n+1$) peut s’écrire sous la forme $n+1=ab$ où $a$ et $b$ sont des entiers de ${2\,,3\,,4\,,\cdots\,,n}$.

On applique $\mathcal{P}_{a}$ et $\mathcal{P}_{b}$ : $a$ et $b$ sont produits de nombres premiers, il en est donc de même de leur produit $n+1$.

L’assertion $\mathcal{P}_{n+1}$ est donc établie.

Ainsi, tout entier naturel $n\geq 2$ est produit de nombres premiers.