# Successió recurrent lineal

En matemàtiques, s'anomena successió recurrent lineal d'ordre p, a tota successió amb valors en un cos K (generalment $\mathbb {C}$ o $\mathbb {R}$) definida per a tot $no\geq n_{0}$ per la relació de recurrència següent :
$a_{0}$, $a_{1}$, …, $a_{p-1}$ sent p escalars fixats de K ($a_{0}$ no nuls), per a tot $no\geq n_{0}$, es té
    $u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}$
Tal successió està completament determinada pels valors dels p primers termes de la successió i per la relació de recurrència.
Les successions recurrents lineals d'ordre 1 s'anomenen més simplement successions geomètriques de raó $a_{0}$. En relació amb les successions recurrents lineals d'ordre 2, Es pot expressar el seu terme general sense haver que recórrer a la recurrència, més precisament fent servir només els dos primers termes, alguns valors constants, algunes operacions elementals de l'aritmètica (addició, subtracció, multiplicació, exponencial) i les funcions sinus i cosinus. Una de les successions d'aquest tipus és la molt cèlebre successió de Fibonacci que es pot expressar a partir de potències fent intervenir la secció àuria. L'estudi de les successions recurrents lineals d'ordre p apel·la a la noció d'espai vectorial i al càlcul matricial.

## Successió recurrent lineal d'ordre 1

Si la relació de recurrència és $u_{n+1}=q\,u_{n}$, el terme general és $u_{n}=u_{n_{0}}q^{n-n_{0}}$

## Successió recurrent lineal d'ordre 2

Sien a i b sent dos escalars fixats de K amb b no nul, la relació de recurrència és
    $u_{n+2}=au_{n+1}+bu_{n}$ (R)
Es demostrarà que el terme general de tal successió és
* $\lambda r_{1}^{n}+\mu r_{2}^{n}$ si $r_{1}$ i $r_{2}$ són les dues arrels diferents del polinomi $X^{2}-aX-b$
* $(\lambda +\mu n)r_{0}^{n}$ si $r_{0}$ és arrel doble del polinomi $X^{2}-aX-b$
* $(\lambda \cos(n\theta )+\mu \sin(n\theta ))\rho ^{n}\,$ per a una successió real quan $\rho e^{i\theta }$ i $\rho e^{-i\theta }$ són les dues arrels complexes (no reals) del polinomi $X^{2}-aX-b$
No es perd la generalitat de la successió suposant que aquesta està definida sobre tot $\mathbb {N}$ i no només a partir de $n_{0}$. En efecte, si una successió (u) no està definida més que a partir de $n_{0}$, indueix la creació d'una successió (v) definida sobre $\mathbb {N}$ posant $v_{n}=u_{n+n_{0}}$.
La idea és llavors de cercar successions geomètriques que verifiquin la recurrència (R). És a Dir buscar escalars r tals que la successió $(r^{n})_{n\in \mathbb {N} }$ verifica (R). Es demostra fàcilment que aquest problema equival a resoldre l'equació de segon grau $r^{2}-ar-b=0\,$. El polinomi $r^{2}-ar-b\,$ s'anomena llavors el polinomi característic de la successió. El seu discriminant és $\Delta =a^{2}+4b\,$. Cal distingir llavors diversos casos, segons el nombre d'arrels del polinomi característic.

### Si el polinomi posseeix dues arrels reals diferents

Siguin $r_{1}$ i $r_{2}$ les dues arrels diferents. Les successions $(r_{1}^{n})_{n\in \mathbb {N} }$ i $(r_{2}^{n})_{n\in \mathbb {N} }$ verifiquen (R) així com tota successió de la qual el terme general seria $\lambda r_{1}^{n}+\mu r_{2}^{n}$ (això manté al caràcter lineal recurrència). Llavors s'han trobat totes les successions que verifiquen (R) ? Una successió que verifica (R) queda completament determinada per la dada de $u_{0}$ i $u_{1}$, n'hi ha prou de demostrar que hom pot sempre trobar $\lambda$ i $\mu$ solucions del sistema
    ${\begin{cases}\lambda +\mu =u_{0}\\\lambda r_{1}+\mu r_{2}=u_{1}\end{cases}}$
Ara bé aquest sistema té per determinant $r_{2}-r_{1}$ no nul. És doncs sempre possible expressar una successió verificant (R) com a combinació lineal successions $(r_{1}^{n})_{n\in \mathbb {N} }$ i $(r_{2}^{n})_{n\in \mathbb {N} }$
Aquesta situació es produeix per a tota successió amb valors reals per a la qual el discriminant $\Delta =a^{2}+4b\,$ és estrictament positiu, o per a tota successió amb valors acomplexes per a la qual discriminant és no nul.

### Si el polinomi posseeix una arrel doble

Si el discriminant és nul, el problema és diferent, ja que no es troba més que un sol valor $r_{0}$, per tant una sola família de successions geomètriques $(\lambda r_{0}^{n})_{n\in \mathbb {N} }$ que verifiquen (R). La idea consisteix llavors a cercar les successions $(\lambda _{n})_{n\in \mathbb {N} }$ tals que, per a tot enter n, $u_{n}=\lambda _{n}r_{0}^{n}$ amb $(u_{n})_{n\in \mathbb {N} }$ que verifiqui (R). Aquest mètode s'anomena el mètode de variació de la constant. S'assegura en principi l'existència de la successió $(\lambda _{n})_{n\in \mathbb {N} }$ que verifica que $r_{0}$ no és mai nul. La relació de recurrència sobre $(u_{n})_{n\in \mathbb {N} }$ es tradueix per una relació de recurrència sobre $(\lambda _{n})_{n\in \mathbb {N} }$:
    $r_{0}^{2}\lambda _{n+2}=ar_{0}\lambda _{n+1}+b\lambda _{n}$
Llavors fent servir el fet que $a^{2}+4b=0$ i que $r_{0}={\dfrac {a}{2}}$, s'obté la relació característica de tota successió aritmètica:
    $\lambda _{n+2}-\lambda _{n+1}=\lambda _{n+1}-\lambda _{n}\,$
La successió $(\lambda _{n})_{n\in \mathbb {N} }$ és per tant una Progressió aritmètica de terme general
    $\lambda _{n}=\lambda +\mu n\,$.
Les successions $(u_{n})_{n\in \mathbb {N} }$ que verifiquen (R) tenen llavors per terme general:
    $u_{n}=(\lambda +\mu n)r_{0}^{n}$.
Aquest resultat s'aplica per a successions amb valors reals o complexes per a les quals el discriminant del polinomi característic és nul.

### Si el polinomi no posseeix cap arrel real

És el cas de les successions amb valors reals per a les quals el discriminant del polinomi característic és estrictament negatiu. Llavors l'equació de segon grau posseeix en $\mathbb {C}$ dues arrels conjugades.
    $r_{1}=\rho e^{i\theta }\,$ i $r_{2}=\rho e^{-i\theta }\,$.
Les successions de terme general $A\rho ^{n}e^{in\theta }+B\rho ^{n}e^{-in\theta }\,$ són successions complexes que verifiquen (R). Entre aquestes, aquelles per a les quals A i B són conjugats, són successions reals. Per tant, les successions de terme general
    $u_{n}=(\lambda \cos(n\theta )+\mu \sin(n\theta ))\rho ^{n}\,$
són successions reals que verifiquen (R) (s'ha pres $A=\lambda /2-i\mu /2$). Llavors s'han trobat totes les successions que verifiquen (R)? Una successió que verifica (R) està completament determinada pel valor de $u_{0}$ i $u_{1}$, n'hi ha prou de demostrar només que hom pot sempre trobar $\lambda$ i $\mu$ solucions del sistema
    ${\begin{cases}\lambda =u_{0}\\\lambda \rho \cos(\theta )+\mu \rho \sin(\theta )=u_{1}\end{cases}}$
Ara bé aquest sistema té per determinant $\rho \sin(\theta )$ no nul. És per tant sempre possible expressar una successió que verifica (R) com a combinació lineal de les successions $(\rho ^{n}\cos(n\theta ))_{n\in \mathbb {N} }$ i $(\rho ^{n}\sin(n\theta ))_{n\in \mathbb {N} }$.

## Successió recurrent d'ordre p
### Subespai vectorial de dimensió p

Si s'anomena $(R_{p})$ la relació de recurrència:
    per a tot enter n, $u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}$
i si s'anomena $E_{R_{p}}$, el conjunt de les successions amb valors a K i que verifiquen $(R_{p})$, es demostra que $E_{R_{p}}$ és un subespai vectorial de l'espai vectorial de les successions amb valors a K. Això és degut a la linearitat de la relació de recurrència.
A més, aquest subespai vectorial és de dimensió p. En efecte, existeix un isomorfisme d'espais vectorials entre $E_{R_{p}}$ i l'espai vectorial $K^{p}\,$: a cada successió (u ) de $E_{R_{p}}$, s'associa el p_uplet $(u_{0},u_{1},\cdots ,u_{p-1})$. N'hi ha prou llavors amb conèixer una família lliure de p successions que verifiquin $(R_{p})$, llavors el conjunt $E_{R_{p}}$ és engendrat per aquesta família lliure.

### Terme general

La cerca del terme general i de les successions particulars s'efectua treballant sobre $K^{p}$. A cada successió $(u_{n})_{n\in \mathbb {N} }$ s'associa la successió $(U_{n})_{n\in \mathbb {N} }$ tal que
    $U_{n}=(u_{n},u_{n+1},\cdots ,u_{n+p-1})$
La relació de recurrència sobre $(u_{n})_{n\in \mathbb {N} }$ indueix una relació de recurrència sobre $(U_{n})_{n\in \mathbb {N} }$
    $U_{n+1}=AU_{n}$
on
    $A={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\ddots &\ddots &\cdots &\vdots \\0&\cdots &\cdots &0&1\\a_{0}&a_{1}&\cdots &\cdots &a_{p-1}\end{pmatrix}}$
Llavors el terme general de la successió U està determinat per
    $U_{n}=A^{n}U_{0}$
Llavors el problema sembla resolt. Però l'autèntica dificultat consisteix en calcular $A^{n}$... Es prefereix determinar més aviat una base de $E_{R_{p}}$.

### Cerca d'una base

El polinomi característic de la matriu A és $P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}$. No és per atzar si es troba per caracteritzar les successions $u=(u_{n})_{n\in \mathbb {N} }$ que verifiquen $R_{p}$.
Es nota f la transformació lineal que, a una successió $u=(u_{n})_{n\in \mathbb {N} }$ associa la successió $v=(v_{n})_{n\in \mathbb {N} }$ definida per $v_{n}=u_{n+1}$. La condició u verifica $R_{p}$ s'ha traduït llavors per P(f)(u) = 0. El conjunt $E_{R_{p}}$ és per tant el nucli de P(f). Si P és un polinomi escindit en K (el que és sempre verdader si $K=\mathbb {C}$), existeixen k arrels $r_{1},r_{2},\cdots ,r_{k}$ i k exponents $\alpha _{1},\alpha _{2},\cdots ,\alpha _{k}$ tals que $P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}$. El nucli de P(f) és llavors la suma directa dels nuclis dels $(f-r_{i}Id)^{\alpha _{i}}$. N'hi ha prou doncs amb trobar una base de cadascun d'aquests nuclis per determinar una base de $E_{R_{p}}$.
Es pot demostrar que tota successió de terme general $Q(n)r_{i}^{n}$ és un element del nucli de $(f-r_{i}Id)^{\alpha _{i}}$ per poc que el grau de Q sigui inferior estrictament a $\alpha _{i}$. Aquesta demostració es fa per recurrència sobre $\alpha _{i}$. Com que les successions $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$, per a j = 0 a $\alpha _{i}-1$ formen una familia lliure de $\alpha _{i}$ elements, la família de totes les successions $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$, per a j = 0 a $\alpha _{i}-1$ i per a i = 1 a k formen una família lliure de $\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p$ elements de $E_{R_{p}}$ (de dimensió p) per tant una base de $E_{R_{p}}$. Els elements de $E_{R_{p}}$ són per tant sumes de successions el terme general de les quals és $Q(n)r_{i}^{n}$ amb grau de Q estrictament inferior a $\alpha _{i}$.

### Tornada a la recurrència d'ordre 2

Si el polinomi característic s'escindeix en $(X-r_{1})(X-r_{2})$ (on $r_{1}\neq r_{2}$) llavors els polinomis Q són de grau 0 i els elements de $E_{R_{2}}$ són successions el terme general de les quals és $\lambda _{1}r_{1}^{n}+\lambda _{2}r_{2}^{n}$.
Si el polinomi característic s'escindeix en $(X-r_{0})^{2}$ llavors els polinomis Q són de grau 1 i els elements de $E_{R_{2}}$ són successions el terme general de les quals és $(\lambda _{1}n+\lambda _{2})r_{0}^{n}$.