# Approfondissement sur les suites numériques/Exercices/Suites récurrentes linéaires
## Exercice 1

(Récurrence linéaire d'ordre 3)
Soit $P(X)=X^{3}-aX^{2}-bX-c\in \mathbb {Z} [X]$, de racines complexes $\alpha ,\beta ,\gamma$ (non nécessairement distinctes). On pose $u_{n}=\alpha ^{n}+\beta ^{n}+\gamma ^{n}$. Montrer que :
* $u_{0},u_{1},u_{2}\in \mathbb {Z}$ ;
* $\forall n\in \mathbb {N} \quad \alpha ^{n+3}=a\alpha ^{n+2}+b\alpha ^{n+1}+c\alpha ^{n}$ ;
* $\forall n\in \mathbb {N} \quad u_{n}\in \mathbb {Z}$.
* $u_{0}=3\in \mathbb {Z}$ et (puisque $(X-\alpha )(X-\beta )(X-\gamma )=X^{3}-aX^{2}-bX-c$) $u_{1}=a\in \mathbb {Z}$ et $-b=\alpha \beta +\alpha \gamma +\beta \gamma$ donc $u_{2}=u_{1}^{2}+2b=a^{2}+2b\in \mathbb {Z}$.
* $\alpha ^{n+3}-a\alpha ^{n+2}-b\alpha ^{n+1}-c\alpha ^{n}=\alpha ^{n}P(\alpha )=0$.
* Montrons par récurrence que $\forall n\in \mathbb {N} \quad u_{n},u_{n+1},u_{n+2}\in \mathbb {Z}$. L'initialisation est la question 1, et l'hérédité ($u_{n},u_{n+1},u_{n+2}\in \mathbb {Z} \Rightarrow u_{n+1},u_{n+2},u_{n+3}\in \mathbb {Z}$, ou encore : $u_{n},u_{n+1},u_{n+2}\in \mathbb {Z} \Rightarrow u_{n+3}\in \mathbb {Z}$) vient de la relation $\forall n\in \mathbb {N} \quad u_{n+3}=au_{n+2}+bu_{n+1}+cu_{n}$, qui se déduit de la question 2 (et de son analogue pour $\beta$ et $\gamma$).

## Exercice 2

Soit $x$ une suite numérique vérifiant une relation de récurrence de la forme
    $x_{n+2}=Sx_{n+1}-Px_{n}$.
On pose $y_{n}=x_{2n}$ et $z_{n}=x_{n}^{2}$.
* En supposant $S^{2}\neq 4P$, trouver une relation de récurrence linéaire d'ordre 2 vérifiée par $y$ et une relation de récurrence linéaire d'ordre 3 vérifiée par $z$, et montrer que cette dernière est aussi vérifiée par $y$.
* Redémontrer directement ces résultats sans supposer $S^{2}\neq 4P$.
* Application : soient $u$ et $v$ deux suites vérifiant :
       $\forall n\in \mathbb {N} \quad u_{n+2}=Su_{n+1}-Pu_{n}\quad {\text{et}}\quad v_{n+2}=sv_{n+1}-pv_{n}$,
    avec $S=s^{2}-2p$ et $P=p^{2}$. On suppose qu'il existe des constantes $a,b,c,d$ telles que la relation
       $au_{n}^{2}+bv_{2n}^{2}+cu_{2n}+dv_{4n}=0$
    soit vérifiée pour $n\in \{0,1,2\}$. Montrer qu'elle l'est alors pour tout $n\in \mathbb {N}$.
1. Si $S^{2}\neq 4P$, le polynôme $X^{2}-SX+P$ a deux racines distinctes $r_{1},r_{2}$, et il existe des constantes $a,b$ telles que
    $\forall n\in \mathbb {N} \quad x_{n}=ar_{1}^{n}+br_{2}^{n}$.
On a alors $y_{n}=aR_{1}^{n}+bR_{2}^{n}$ pour $R_{1}:=r_{1}^{2},R_{2}:=r_{2}^{2}$, racines du polynôme $\left(X-r_{1}^{2}\right)\left(X-r_{2}^{2}\right)=X^{2}-\left(S^{2}-2P\right)X+P^{2}$. Par conséquent,
On a de plus $z_{n}=\left(ar_{1}^{n}+br_{2}^{n}\right)^{2}=a^{2}R_{1}^{n}+b^{2}R_{2}^{n}+2abR_{3}^{n}$ pour $R_{3}:=r_{1}r_{2}=P$. Les trois nombres $R_{1},R_{2},R_{3}$ sont racines du polynôme
    $\left(X^{2}-\left(S^{2}-2P\right)X+P^{2}\right)\left(X-P\right)=X^{3}+\left(P-S^{2}\right)\left(X^{2}-PX\right)-P^{3}$.
Par conséquent,
La suite $y$ vérifie aussi cette relation, puisque $y_{n}=aR_{1}^{n}+bR_{2}^{n}+0R_{3}^{n}$.
2. On pourrait effectuer les calculs ci-dessus de façon générique en considérant $S,P,x_{0},x_{1}$ comme quatre indéterminées polynomiales, mais on peut aussi, plus élémentairement, vérifier « à la main » les relations trouvées :
    ${\begin{aligned}y_{n+2}+P^{2}y_{n}&=Sx_{2n+3}-Px_{2n+2}+P\left(Sx_{2n+1}-x_{2n+2}\right)\\&=S\left(x_{2n+3}+Px_{2n+1}\right)-2Px_{2n+2}\\&=\left(S^{2}-2P\right)y_{n+1}\end{aligned}}$
    ${\begin{aligned}z_{n+3}-P^{3}z_{n}&=\left(Sx_{n+2}-Px_{n+1}\right)^{2}-P\left(Sx_{n+1}-x_{n+2}\right)^{2}\\&=\left(S^{2}-P\right)\left(z_{n+2}-Pz_{n+1}\right)\end{aligned}}$
    ${\begin{aligned}y_{n+3}-P^{3}y_{n}&=\left(S^{2}-2P\right)y_{n+2}-P^{2}y_{n+1}-P\left(\left(S^{2}-2P\right)y_{n+1}-y_{n+2}\right)\\&=\left(S^{2}-P\right)\left(y_{n+2}-Py_{n+1}\right)\end{aligned}}$
3. D'après ce qui précède, la suite $w$ définie par $w_{n}:=v_{2n}$ vérifie la même récurrence d'ordre 2 que la suite $u$, et les quatre suites $\left(u_{n}^{2}\right),\left(w_{n}^{2}\right),\left(u_{2n}\right),\left(w_{2n}\right)$ vérifient une même récurrence linéaire d'ordre 3.

## Exercice 3

Soit $x$ une suite numérique vérifiant une relation de récurrence de la forme
    $x_{n+2}=Sx_{n+1}-Px_{n}$.
On suppose que $S^{2}\neq 4P$ et $x_{0}=0$.
Montrer qu'il existe des constantes $A$, $B$ et $C$ telles que $x_{n+1}^{3}+Ax_{n}^{3}+Bx_{n-1}^{3}=Cx_{3n}$ (pour tout $n\geq 1$).
D'après les hypothèses, $x_{n}=a(r^{n}-r'^{n})$ avec $r+r'=S$ et $rr'=P$. On peut de plus supposer $P\neq 0$ car le cas d'une suite géométrique est immédiat.
    $x_{n}^{3}=a^{3}\left(r^{3n}-r^{3n}-3P^{n}(r^{n}-r'^{n})\right)=a^{2}(x_{3n}-3P^{n}x_{n})$
donc
    $x_{n+1}^{3}+Ax_{n}^{3}+Bx_{n-1}^{3}=a^{2}\left(x_{3n+3}+Ax_{3n}+Bx_{3n-3}-3P^{n}(Px_{n+1}+Ax_{n}+BP^{-1}x_{n-1})\right)$.
En choisissant $A=-SP$ et $B=P^{3}$, il reste :
    $x_{n+1}^{3}-SPx_{n}^{3}+P^{3}x_{n-1}^{3}=a^{2}\left(x_{3n+3}-SPx_{3n}+P^{3}x_{3n-3}\right)$.
Mais $r$ et $r'$ sont solutions de $S^{3}=x^{3}+{\frac {P^{3}}{x^{3}}}+3SP$. Par conséquent, $x_{k+3}+P^{3}x_{k-3}=(S^{2}-3SP)x_{k}$ et il reste en fait seulement :
    $x_{n+1}^{3}-SPx_{n}^{3}+P^{3}x_{n-1}^{3}=a^{2}(S^{2}-4SP)x_{3n}=x_{1}x_{2}x_{3n}$.

## Exercice 4

Soit $x$ une suite numérique. On pose $y_{j}=x_{j+1}^{2}-x_{j}x_{j+2}$ et $z_{j}=x_{j}x_{j+3}-x_{j+1}x_{j+2}$.
* On suppose : $\forall k\in \mathbb {N} \quad x_{k+2}-Sx_{k+1}+Px_{k}=0\quad (*)$.
** Montrer que la suite $y$ est géométrique et que $z=-Sy$.
** En déduire : $\forall i\geq 4\quad x_{i}y_{i-4}+x_{i-1}z_{i-4}+x_{i-2}y_{i-3}=0\quad (**)$.
* Réciproquement, on suppose, pour un certain $n\geq 4$, que $(**)$ est vérifiée pour $4\leq i\leq n$. On suppose de plus $y_{0}\neq 0$ et, si $n>4$, $P\neq 0$. Montrer que si $(*)$ est vérifiée pour $k=0$ et $k=1$, alors elle l'est pour tout $k\leq n-2$.
** $y_{n+1}=x_{n+2}(Sx_{n+1}-Px_{n})-x_{n+1}(Sx_{n+2}-Px_{n+1})=-Px_{n+2}Px_{n}+Px_{n+1}^{2}=Py_{n}$ et $z_{n}=x_{n}(Sx_{n+2}-Px_{n+1})-x_{n+1}(Sx_{n+1}-Px_{n})=S(x_{n}x_{n+2}-x_{n+1}^{2})=-Sy_{n}$.
** $x_{i}y_{i-4}+x_{i-1}z_{i-4}+x_{i-2}y_{i-3}=x_{i}P^{i-4}y_{0}-x_{i-1}SP^{i-4}y_{0}+x_{i-2}P^{i-3}y_{0}=P^{i-4}y_{0}\left(x_{i}-Sx_{i-1}+Px_{i-2}\right)=0$.
* Soit $4\leq i\leq n$ tel que $(*)$ soit vérifiée pour tout $k<i-2$, montrons qu'elle l'est encore pour $k=i-2$. On déduit de l'hypothèse de récurrence ci-dessus, comme dans la question 1.1 : $\forall j\leq i-3\quad y_{j}=P^{j}y_{0}$ et $\forall j\leq i-4\quad z_{j}=-SP^{j}y_{0}$. L'hypothèse $(**)$ se réécrit alors : $P^{i-4}y_{0}\left(x_{i}-Sx_{i-1}+Px_{i-2}\right)=0$, et l'on conclut en simplifiant par $P^{i-4}y_{0}$.
| Convergence | Suites et modélisation (exemples en biologie) |