Récurrences linéaires d'ordre deux

Comme application des notions de ce chapitre, nous proposons d'étudier l'ensemble des solutions de l'équation de récurrence suivante :

$$({\cal E}) \qquad \forall n\in \mathbb{N} \;,\quad u_{n+2}=\alpha u_{n+1}+\beta u_n\;,$$

où $\alpha$ et $\beta$ sont deux réels fixés. L'exemple le plus simple est l'équation définissant les nombres de Fibonacci, $u_{n+2}=u_{n+1}+u_{n}$. Nous notons $E$ l'ensemble des suites de réels qui vérifient $({\cal E})$. Dire que $({\cal E})$ est linéaire revient à dire que $E$ est un espace vectoriel.

Proposition 12   L'ensemble $E$ des suites de réels vérifiant $({\cal E})$ est un espace vectoriel de dimension $2$.

Démonstration : Commençons par vérifier que $E$ est un sous-espace vectoriel de l'ensemble des suites de réels. Nous en donnerons ensuite une base.

Soient $(u_n)$ et $(v_n)$ deux suites vérifiant $({\cal E})$, $\lambda,\mu$ deux réels.

$$u_{n+2}=\alpha u_{n+1}+\beta u_{n}$$   et$$\quad v_{n+2}=\alpha v_{n+1}+\beta v_{n}$$

impliquent :

$$\lambda u_{n+2}+\mu v_{n+2}=\alpha (\lambda u_{n+1}+\mu v_{n+1})+ \beta (\lambda u_{n}+\mu v_n)$$

Donc $(\lambda u_n+\mu v_n)$ vérifie $({\cal E})$. D'où le résultat en appliquant le théorème 2. On peut aussi démontrer que l'application qui à une suite $(u_n)$ quelconque associe la suite de terme général $v_n=u_{n+2}-\alpha u_{n+1}-\beta u_n$ est une application linéaire. L'ensemble $E$ est le noyau de cette aplication. C'est donc un sous-espace vectoriel de $\mathbb{R}^\mathbb{N}$, par le théorème 6. Considérons maintenant les deux suites $(b_n)$ et $(b'_n)$, vérifiant $({\cal E})$ et telles que

$$b_0=1 ,\;b_1=0$$   et$$\quad b'_0=0 ,\;b'_1=1\;.$$

Soit $(u_n)$ une suite quelconque vérifiant $({\cal E})$. La suite $(u_n)$ est définie de façon unique par la donnée de $u_0,u_1 \in \mathbb{R}$ et l'équation $({\cal E})$. Donc la suite $(u_n)$ est égale à la combinaison linéaire $u_0(b_n)+u_1(b'_n)$ : la famille $\big( (b_n), (b'_n) \big)$ est génératrice. Supposons que $(u_n)$ soit la suite nulle. Alors $u_0=u_1=0$. Donc la famille $\big( (b_n), (b'_n) \big)$ est libre : c'est une base. $\square$

Pour trouver une expression explicite aux solutions de $({\cal E})$, nous allons trouver une autre base. Nous commençons par écarter le cas où $\alpha=\beta=0$ : dans ce cas, les suites solutions de $({\cal E})$ sont nulles à partir du rang 2. Nous supposons désormais que $\alpha$ et $\beta$ ne sont pas tous les deux nuls. Cherchons quelles suites géométriques vérifient $({\cal E})$. Supposons que $(r^n)$ vérifie $({\cal E})$. Alors,

$$\forall n\in \mathbb{N} \;,\quad r^{n+2}=\alpha r^{n+1}+\beta r^n\;.$$

C'est vrai si $r$ est nul, ou bien s'il est solution de l'équation du second degré suivante, qu'on appelle l'équation caractéristique associée.

$$(ECA) \qquad r^2=\alpha r+\beta\;.$$

Théorème 8   Si l'équation caractéristique associée possède

1. deux racines réelles distinctes $r_1$ et $r_2$, alors $\big( (r_1^n),(r_2^n) \big)$ est une base de $E$ :
   $$E = \big\{ (\lambda r_1^n + \mu r_2^n) ,\; (\lambda,\mu)\in \mathbb{R}^2 \big\}.$$

2. une racine double $r$, alors $\big( (r^n),(n r^n) \big)$ est une base de $E$ :
   $$E = \big\{ (\lambda r^n + \mu n r^n) ,\; (\lambda,\mu)\in \mathbb{R}^2 \big\}.$$

3. deux racines complexes conjuguées $\rho \mathrm{e}^{\mathrm{i}\theta}$ et $\rho \mathrm{e}^{-\mathrm{i}\theta}$, alors $\big( (\rho^n \cos(n\theta)),(\rho^n\sin(n\theta)) \big)$ est une base de $E$ :
   $$E = \big\{ (\lambda \rho^n \cos(n\theta) + \mu \rho^n \sin(n\theta)) ,\; (\lambda,\mu)\in \mathbb{R}^2 \big\}.$$

Démonstration : Puisque l'espace vectoriel $E$ est de dimension $2$, il suffit dans chacun des trois cas de montrer que les deux suites proposées vérifient $({\cal E})$ et forment une famille libre.

Dans le premier cas, les deux suites vérifient $({\cal E})$ car $r_1$ et $r_2$ sont racines de $(ECA)$. Pour montrer qu'elles forment une famille libre, supposons que la suite $(\lambda r_1^n +\mu r_2^n)$ soit nulle. Les deux premiers termes sont :

$$\lambda+\mu=0$$   et$$\quad \lambda r_1+\mu r_2=0$$

Puisque $r_1\neq r_2$, ce système de deux équations a une solution unique, $\lambda=\mu=0$.

Dans le second cas la racine double est $r=\alpha/2$ et elle est non nulle, le cas $\alpha=\beta=0$ étant écarté. Il est évident que $(r^n)$ vérifie $({\cal E})$. On le vérifie facilement pour $(nr^n)$. Pour montrer que la famille est libre, supposons que la suite $(\lambda r^n+\mu nr^n)$ soit nulle. Les deux premiers termes sont :

$$\lambda = 0$$   et$$\quad \lambda r +\mu r = 0\;.$$

Donc (puisque $r\neq 0$), $\lambda=\mu=0$.

Traitons maintenant le dernier cas : $(ECA)$ a deux racines complexes conjuguées $\rho \mathrm{e}^{\mathrm{i}\theta}$ et $\rho \mathrm{e}^{-\mathrm{i}\theta}$. Les suites (complexes) $(\rho^n \mathrm{e}^{n\mathrm{i}\theta})$ et $(\rho^n \mathrm{e}^{-n\mathrm{i}\theta})$ vérifient $({\cal E})$. Leur somme et leur différence sont :

$$\rho^n \mathrm{e}^{n\mathrm{i}\theta} +\rho^n \mathrm{e}^{-n\mathrm{i}\theta}= 2\rho^n \cos(n\theta)$$   et$$\quad \rho^n \mathrm{e}^{n\mathrm{i}\theta} -\rho^n \mathrm{e}^{-n\mathrm{i}\theta}= 2\mathrm{i}\rho^n \sin(n\theta)\;.$$

On en déduit que les deux suites proposées vérifient $({\cal E})$. Pour montrer que la famille est libre, supposons que la suite $(\lambda \rho^n\cos(n\theta)+\mu \rho^n\sin(n\theta))$ soit nulle. Les deux premiers termes sont :

$$\lambda = 0\;,\quad \lambda \rho\cos(\theta)+\mu\rho\sin(\theta)=0\;.$$

On en déduit donc que $\mu\rho\sin(\theta)=0$, donc $\mu=0$ car $\rho\sin(\theta)$ est non nul (sinon les racines de $(ECA)$ seraient réelles).$\square$

Comme premier exemple, considérons l'équation définissant les nombres de Fibonacci :

$$({\cal E}) \qquad \forall n\in \mathbb{N} \;,\quad u_{n+2}=u_{n+1}+u_n\;.$$

L'équation caractéristique associée est

$$(ECA) \qquad r^2=r+1\;.$$

Elle a deux racines réelles distinctes, $\phi$ et $-1/\phi$, où $\phi$ est le nombre d'or :

$$\phi = \frac{1+\sqrt{5}}{2}\quad,\quad -\frac{1}{\phi} = \frac{1-\sqrt{5}}{2}\;.$$

L'ensemble des suites réelles vérifiant $({\cal E})$ est donc

$$\left\{ \left( \lambda \left(\frac{1+\sqrt{5}}{2}\right)^n+\... ...{1-\sqrt{5}}{2}\right)^n \right) \;,\quad\lambda,\mu\in\mathbb{R} \right\}.$$

Les nombres de Fibonacci sont définis par $({\cal E})$, avec $u_0=1$ et $u_1=1$. Pour calculer les coordonnées $\lambda$ et $\mu$ de cette suite, il faut résoudre le système

$$\left\{ \begin{array}{lcl} \lambda+\mu&=&1 [1.5ex] \lambda\phi-\mu/\phi&=&1 \end{array}\right.$$

On en déduit l'expression suivante du $n$-ième nombre de Fibonacci :

$$u_n = \frac{1}{2^{n+1}\sqrt{5}}\left((1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}\right)\;.$$

(Persuadez-vous que $u_n$ est bien un entier !) Considérons maintenant l'équation suivante.

$$({\cal E}) \qquad \forall n\in \mathbb{N} \;,\quad u_{n+2}=-u_{n+1}-u_n\;.$$

L'équation caractéristique associée est :

$$(ECA) \qquad r^2=-r-1\;.$$

Ses racines sont :

$$j=-\frac{1}{2} + \mathrm{i}\frac{\sqrt 3}{2}=\mathrm{e}^{2\mathrm{i}\pi/3}$$   et$$\quad \overline j =-\frac{1}{2} - \mathrm{i}\frac{\sqrt 3}{2}=\mathrm{e}^{-2\mathrm{i}\pi/3}$$

Toute solution réelle de l'équation de récurrence s'écrit :

$$(u_n) = \left( \lambda \cos(n2\pi/3)+ \mu \sin(n2\pi/3) \right)\;.$$

Les solutions sont périodiques de période $3$.