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

Article principal: Successió geomètrica

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}$.