Récurrence double

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}$$

Récurrence forte

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.

Saïd BENLAADAM
Je suis ingénieur télécoms de formation et j’exerce ce métier depuis toujours. Je reste cependant passionné par les mathématiques et très proche de ce domaine.
À travers mathsland, je m’enrichis chaque jour au contact de personnes remarquables, passionnées et passionnantes.

Réagir à ce sujet :

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser les balises HTML ci-dessous :

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>