# 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}}$.
* Vérifier que
    $\forall z,z'\in \mathbb {Q} \left({\sqrt {2}}\right)\quad {\overline {z}}{\overline {z'}}={\overline {zz'}}$.
* 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}}}$.
* Calculer $a$ et $b$.
* Vérifier que
    $a^{2}-a+b^{2}=0\quad {\text{et}}\quad a{\overline {a}}+b{\overline {b}}=0$.
* En déduire que
    $\forall n\in \mathbb {N} \quad u_{n}^{2}+v_{2n}^{2}=u_{2n}$.
* 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'}}$.
* 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.
** $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}}$.
* $a^{2}-a=\left(a-1\right)a=-{\overline {a}}a=-{\frac {1}{8}}=-b^{2}=b{\overline {b}}$.
* $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$.
* Calculer les 10 premiers termes de cette suite.
* Proposer un algorithme qui calcule le n-ième terme de la suite. Évaluer son temps d'exécution.
* 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 '$.
* Donner l’expression de $F_{n}$ en fonction de n et des deux racines (cette formule est appelée formule de Binet).
* Quelle est la limite du rapport ${\frac {F_{n+1}}{F_{n}}}$ ? Ce résultat est dû à Kepler.
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
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})$
    $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}$ ?
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$.
| Récurrence affine d'ordre 2 | Étude d'une suite récurrente |