Approfondissement sur les suites numériques/Exercices/Récurrence linéaire d'ordre 2

Exercice 1

Soient $u$ et $v$ les deux suites définies par :

$u_{0}=1,\quad u_{1}=5,\quad \forall n\in \mathbb {N} \quad u_{n+2}=34u_{n+1}-u_{n}$ ;

$v_{0}=0,\quad v_{1}=2,\quad \forall n\in \mathbb {N} \quad v_{n+2}=6v_{n+1}-v_{n}$.

On note $\mathbb {Q} \left({\sqrt {2}}\right)$ l'ensemble des réels de la forme $z=x+y{\sqrt {2}}$ avec $x,y\in \mathbb {Q}$, et pour un tel nombre $z$, on note ${\overline {z}}=x-y{\sqrt {2}}$.

1. Vérifier que

   $\forall z,z'\in \mathbb {Q} \left({\sqrt {2}}\right)\quad {\overline {z}}{\overline {z'}}={\overline {zz'}}$.

2. Montrer qu'il existe trois nombres $a,b,r\in \mathbb {Q} \left({\sqrt {2}}\right)$ tels que

   $\forall n\in \mathbb {N} \quad u_{n}=ar^{2n}+{\overline {ar^{2n}}}\quad {\text{et}}\quad v_{n}=br^{n}+{\overline {br^{n}}}$.

3. Calculer $a$ et $b$.
4. Vérifier que

   $a^{2}-a+b^{2}=0\quad {\text{et}}\quad a{\overline {a}}+b{\overline {b}}=0$.

5. En déduire que

   $\forall n\in \mathbb {N} \quad u_{n}^{2}+v_{2n}^{2}=u_{2n}$.

Solution

1. Soient $z=x+y{\sqrt {2}}$ et $z'=x'+y'{\sqrt {2}}$, avec $x,y,x',y'\in \mathbb {Q}$. Alors,

   ${\overline {zz'}}={\overline {\left(xx'+2yy'\right)+\left(xy'+x'y\right){\sqrt {2}}}}=\left(xx'+2yy'\right)-\left(xy'+x'y\right){\sqrt {2}}={\overline {z}}{\overline {z'}}$.

2. Les racines de $X^{2}-6X+1$ sont $r:=3+2{\sqrt {2}}$ et ${\overline {r}}$, et celles de $X^{2}-34X+1$ sont $17+12{\sqrt {2}}=r^{2}$ et ${\overline {r^{2}}}$.

   Il existe donc $a,a',b,b'$ tels que (compte tenu de la question précédente) :

   $\forall n\in \mathbb {N} \quad u_{n}=ar^{2n}+a'{\overline {r^{2n}}}\quad {\text{et}}\quad v_{n}=br^{n}+b'{\overline {r^{n}}}$.

   De plus, puisque les deux suites sont (par récurrence) à valeurs entières, on a $a,b\in \mathbb {Q} \left({\sqrt {2}}\right)$, $a'={\overline {a}}$ et $b'={\overline {b}}$, ce qui donne bien les formules annoncées.

3. • $1=u_{0}=a+{\overline {a}}$ et $5=u_{1}=ar^{2}+{\overline {a}}{\overline {r^{2}}}$ donc $a={\frac {{\overline {r^{2}}}-5}{{\overline {r^{2}}}-r^{2}}}={\frac {12-12{\sqrt {2}}}{-24{\sqrt {2}}}}={\frac {2-{\sqrt {2}}}{4}}$.
   • $0=v_{0}=b+{\overline {b}}$ et $2=v_{1}=br+{\overline {b}}{\overline {r}}$ donc $b={\frac {-2}{{\overline {r}}-r}}={\frac {-2}{-4{\sqrt {2}}}}={\frac {\sqrt {2}}{4}}$.
4. $a^{2}-a=\left(a-1\right)a=-{\overline {a}}a=-{\frac {1}{8}}=-b^{2}=b{\overline {b}}$.
5. $u_{n}^{2}+v_{2n}^{2}-u_{2n}=\left(ar^{2n}+{\overline {ar^{2n}}}\right)^{2}+\left(br^{2n}+{\overline {br^{2n}}}\right)^{2}-\left(ar^{4n}+{\overline {ar^{4n}}}\right)=\left(a^{2}-a+b\right)r^{4n}+{\overline {\left(a^{2}-a+b\right)r^{4n}}}+2\left(a{\overline {a}}+b{\overline {b}}\right)\left(r{\overline {r}}\right)^{2n}=0r^{4n}+{\overline {0r^{4n}}}+2.0\left(r{\overline {r}}\right)^{2n}=0$

 

Suite de Fibonacci

La suite de Fibonacci est une célèbre suite de nombres entiers, liés par la récurrence : $F_{n+2}=F_{n+1}+F_{n}$ avec pour premiers termes $F_{1}=F_{2}=1$.

1. Calculer les 10 premiers termes de cette suite.
2. Proposer un algorithme qui calcule le n-ième terme de la suite. Évaluer son temps d'exécution.
3. Calculer les racines du polynôme caractéristique associé : la plus grande est appelée nombre d'or et notée $\varphi$. L'autre est notée $\varphi '$.
4. Donner l’expression de $F_{n}$ en fonction de n et des deux racines (cette formule est appelée formule de Binet).
5. Quelle est la limite du rapport ${\frac {F_{n+1}}{F_{n}}}$ ? Ce résultat est dû à Kepler.

Solution

1. ${\begin{array}{|c|c|c|c|c|c|c|c|c|c|}F_{1}&F_{2}&F_{3}&F_{4}&F_{5}&F_{6}&F_{7}&F_{8}&F_{9}&F_{10}\\\hline 1&1&2&3&5&8&13&21&34&55\end{array}}$

2. Fibonnacci(n)=
Si n=1 Alors Retourner 1.
Si n=2 Alors Retourner 1.
V <- [1,1]
c <- 0
Pour i de 3 à n Faire


c <- V[1]+V[2]

V[2] <- V[1]

V[1] <- c

FinPour
Retourner V[1]

Ce programme est d'une complexité linéaire en $n$.

3. Le polynôme caractéristique associé à cette suite est $F(X)=X^{2}-X-1$.

Son discriminant vaut $\Delta =1-4.1.(-1)=5$, donc $F$ admet deux racines réelles distinctes :

• $\varphi ={\frac {1+{\sqrt {5}}}{2}}$
• $\varphi '={\frac {1-{\sqrt {5}}}{2}}$

4. Le polynôme caractéristique admettant deux racines simples, on sait alors que les termes de la suite s'expriment de la façon suivante :

$F_{n}=\alpha \varphi ^{n}+\beta \varphi '^{n}$.

Il reste à déterminer α et β. Or :

$F_{1}=1=\alpha \varphi +\beta \varphi ',\quad F_{2}=1=\alpha \varphi ^{2}+\beta \varphi '^{2}$,

ce qui donne :

$\alpha ={\frac {\varphi '-1}{\varphi (\varphi '-\varphi )}}={\frac {1}{\sqrt {5}}}\quad ,\quad \beta ={\frac {1-\varphi }{\varphi '(\varphi '-\varphi )}}=-{\frac {1}{\sqrt {5}}}$

donc, finalement :

$F_{n}={\frac {\varphi ^{n}-\varphi '^{n}}{\sqrt {5}}}$.

5. En utilisant la formule précédente, il vient ${\frac {F_{n+1}}{F_{n}}}={\frac {\varphi ^{n+1}-\varphi '^{n+1}}{\varphi ^{n}-\varphi '^{n}}}$.

Comme $|\varphi |>1\ {\text{et}}\ |\varphi '|<1$, on en déduit :

${\frac {F_{n+1}}{F_{n}}}\sim _{n\to +\infty }{\frac {\varphi ^{n+1}}{\varphi ^{n}}}=\varphi$

donc $\lim _{n\to +\infty }{\frac {F_{n+1}}{F_{n}}}=\varphi$.

 

Identités remarquables

Référence : Robert C. Johnson, « Fibonacci numbers and matrices », sur Université de Durham, 2009, p. 40 (A.10).

Soient $a$ et $b$ deux éléments d'un corps commutatif K, avec $b\neq 0$.

Montrer que si une suite $u$ (à valeurs dans K) vérifie

$\forall n\in \mathbb {N} \quad u_{n+2}=au_{n+1}+bu_{n}\quad (R)$

alors, elle peut être étendue aux indices négatifs et reliée aux puissances d'une certaine matrice inversible $P$ par :

$\forall n\in \mathbb {Z} \quad {\begin{pmatrix}u_{n+1}\\u_{n}\end{pmatrix}}=P^{n}{\begin{pmatrix}u_{1}\\u_{0}\end{pmatrix}}.$

et que pour $v$ égale à $u$ ou à toute autre suite vérifiant la même relation de récurrence $(R)$ et pour tous entiers $i,j,k,l$ et $r$ :

$i+j=k+l\Rightarrow u_{i+r}v_{j+r}-u_{k+r}v_{l+r}=(-b)^{r}(u_{i}v_{j}-u_{k}v_{l})$.

Solution

$P:={\begin{pmatrix}a&b\\1&0\end{pmatrix}}$.

La matrice

$Q:={\begin{pmatrix}u_{1}&bu_{0}\\u_{0}&bu_{-1}\end{pmatrix}}$

vérifie

$\forall n\in \mathbb {Z} \quad {\begin{pmatrix}u_{n+1}&bu_{n}\\u_{n}&bu_{n-1}\end{pmatrix}}=P^{n}Q$

et commute avec $P$, donc

${\begin{pmatrix}u_{i+1}&bu_{i}\\u_{i}&bu_{i-1}\end{pmatrix}}{\begin{pmatrix}v_{j+1}\\v_{j}\end{pmatrix}}=P^{i}QP^{j}{\begin{pmatrix}v_{1}\\v_{0}\end{pmatrix}}=P^{k}QP^{l}{\begin{pmatrix}v_{1}\\v_{0}\end{pmatrix}}={\begin{pmatrix}u_{k+1}&bu_{k}\\u_{k}&bu_{k-1}\end{pmatrix}}{\begin{pmatrix}v_{l+1}\\v_{l}\end{pmatrix}}.$

On en déduit

$u_{i+1}v_{j+1}-u_{k+1}v_{l+1}=-b(u_{i}v_{j}-u_{k}v_{l})$

et l'on conclut par récurrence sur $|r|$.

 

Remarques

En particulier, si $u_{0}=0$ alors

• $\forall m,n,r\in \mathbb {Z} \quad u_{n}v_{m+r}-u_{r}v_{m+n}=(-b)^{r}u_{n-r}v_{m}$ ;
• en particulier, $\forall m,n\in \mathbb {Z} \quad u_{1}v_{m+n}=u_{n}v_{m+1}+bu_{n-1}v_{m}$.

Ceci s'applique par exemple à la suite de Fibonacci $(F_{n})$ (voir supra), qui vérifie donc :

• $\forall m,n,r\in \mathbb {Z} \quad F_{n}F_{m+r}-F_{r}F_{m+n}=(-1)^{r}F_{n-r}F_{m}$ ;
• en particulier, $\forall m,n\in \mathbb {Z} \quad F_{m+n}=F_{n}F_{m+1}+F_{n-1}F_{m}$.

Points communs

Quelles sont les valeurs communes aux deux suites $v$ et $w$ définies par :

• $v_{0}=1,\quad v_{1}=1\quad {\text{et}}\quad \forall n\in \mathbb {N} \quad v_{n+2}=v_{n+1}+2v_{n}$ ;
• $w_{0}=1,\quad w_{1}=7\quad {\text{et}}\quad \forall n\in \mathbb {N} \quad w_{n+2}=2w_{n+1}+3w_{n}$ ?

Solution

Modulo $8$, $w_{n}$ est alternativement congru à $1$ et à $-1$ tandis que pour $n\geq 2$, $v_{n}$ est alternativement congru à $3$ et à $-3$. La seule valeur commune est donc $v_{0}=v_{1}=w_{0}=1$.