Successió recurrent lineal

En matemàtiques, s'anomena successió recurrent lineal d'ordre p, a tota successió amb valors en un cos K (generalment ${\displaystyle \mathbb {C} }$ o ${\displaystyle \mathbb {R} }$) definida per a tot ${\displaystyle no\geq n_{0}}$ per la relació de recurrència següent :

${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, …, ${\displaystyle a_{p-1}}$ sent p escalars fixats de K (${\displaystyle a_{0}}$ no nuls), per a tot ${\displaystyle no\geq n_{0}}$, es té

${\displaystyle 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ó ${\displaystyle 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 ${\displaystyle u_{n+1}=q\,u_{n}}$, el terme general és ${\displaystyle 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

${\displaystyle u_{n+2}=au_{n+1}+bu_{n}}$ (R)

Es demostrarà que el terme general de tal successió és

• ${\displaystyle \lambda r_{1}^{n}+\mu r_{2}^{n}}$ si ${\displaystyle r_{1}}$ i ${\displaystyle r_{2}}$ són les dues arrels diferents del polinomi ${\displaystyle X^{2}-aX-b}$
• ${\displaystyle (\lambda +\mu n)r_{0}^{n}}$ si ${\displaystyle r_{0}}$ és arrel doble del polinomi ${\displaystyle X^{2}-aX-b}$
• ${\displaystyle (\lambda \cos(n\theta )+\mu \sin(n\theta ))\rho ^{n}\,}$ per a una successió real quan ${\displaystyle \rho e^{i\theta }}$ i ${\displaystyle \rho e^{-i\theta }}$ són les dues arrels complexes (no reals) del polinomi ${\displaystyle X^{2}-aX-b}$

No es perd la generalitat de la successió suposant que aquesta està definida sobre tot ${\displaystyle \mathbb {N} }$ i no només a partir de ${\displaystyle n_{0}}$. En efecte, si una successió (u) no està definida més que a partir de ${\displaystyle n_{0}}$, indueix la creació d'una successió (v) definida sobre ${\displaystyle \mathbb {N} }$ posant ${\displaystyle 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ó ${\displaystyle (r^{n})_{n\in \mathbb {N} }}$ verifica (R). Es demostra fàcilment que aquest problema equival a resoldre l'equació de segon grau ${\displaystyle r^{2}-ar-b=0\,}$. El polinomi ${\displaystyle r^{2}-ar-b\,}$ s'anomena llavors el polinomi característic de la successió. El seu discriminant és ${\displaystyle \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 ${\displaystyle r_{1}}$ i ${\displaystyle r_{2}}$ les dues arrels diferents. Les successions ${\displaystyle (r_{1}^{n})_{n\in \mathbb {N} }}$ i ${\displaystyle (r_{2}^{n})_{n\in \mathbb {N} }}$ verifiquen (R) així com tota successió de la qual el terme general seria ${\displaystyle \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 ${\displaystyle u_{0}}$ i ${\displaystyle u_{1}}$, n'hi ha prou de demostrar que hom pot sempre trobar ${\displaystyle \lambda }$ i ${\displaystyle \mu }$ solucions del sistema

${\displaystyle {\begin{cases}\lambda +\mu =u_{0}\\\lambda r_{1}+\mu r_{2}=u_{1}\end{cases}}}$

Ara bé aquest sistema té per determinant ${\displaystyle r_{2}-r_{1}}$ no nul. És doncs sempre possible expressar una successió verificant (R) com a combinació lineal successions ${\displaystyle (r_{1}^{n})_{n\in \mathbb {N} }}$ i ${\displaystyle (r_{2}^{n})_{n\in \mathbb {N} }}$

Aquesta situació es produeix per a tota successió amb valors reals per a la qual el discriminant ${\displaystyle \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 ${\displaystyle r_{0}}$, per tant una sola família de successions geomètriques ${\displaystyle (\lambda r_{0}^{n})_{n\in \mathbb {N} }}$ que verifiquen (R). La idea consisteix llavors a cercar les successions ${\displaystyle (\lambda _{n})_{n\in \mathbb {N} }}$ tals que, per a tot enter n, ${\displaystyle u_{n}=\lambda _{n}r_{0}^{n}}$ amb ${\displaystyle (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ó ${\displaystyle (\lambda _{n})_{n\in \mathbb {N} }}$ que verifica que ${\displaystyle r_{0}}$ no és mai nul. La relació de recurrència sobre ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ es tradueix per una relació de recurrència sobre ${\displaystyle (\lambda _{n})_{n\in \mathbb {N} }}$:

${\displaystyle r_{0}^{2}\lambda _{n+2}=ar_{0}\lambda _{n+1}+b\lambda _{n}}$

Llavors fent servir el fet que ${\displaystyle a^{2}+4b=0}$ i que ${\displaystyle r_{0}={\dfrac {a}{2}}}$, s'obté la relació característica de tota successió aritmètica:

${\displaystyle \lambda _{n+2}-\lambda _{n+1}=\lambda _{n+1}-\lambda _{n}\,}$

La successió ${\displaystyle (\lambda _{n})_{n\in \mathbb {N} }}$ és per tant una Progressió aritmètica de terme general

${\displaystyle \lambda _{n}=\lambda +\mu n\,}$.

Les successions ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ que verifiquen (R) tenen llavors per terme general:

${\displaystyle 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 ${\displaystyle \mathbb {C} }$ dues arrels conjugades.

${\displaystyle r_{1}=\rho e^{i\theta }\,}$ i ${\displaystyle r_{2}=\rho e^{-i\theta }\,}$.

Les successions de terme general ${\displaystyle 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

${\displaystyle u_{n}=(\lambda \cos(n\theta )+\mu \sin(n\theta ))\rho ^{n}\,}$

són successions reals que verifiquen (R) (s'ha pres ${\displaystyle 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 ${\displaystyle u_{0}}$ i ${\displaystyle u_{1}}$, n'hi ha prou de demostrar només que hom pot sempre trobar ${\displaystyle \lambda }$ i ${\displaystyle \mu }$ solucions del sistema

${\displaystyle {\begin{cases}\lambda =u_{0}\\\lambda \rho \cos(\theta )+\mu \rho \sin(\theta )=u_{1}\end{cases}}}$

Ara bé aquest sistema té per determinant ${\displaystyle \rho \sin(\theta )}$ no nul. És per tant sempre possible expressar una successió que verifica (R) com a combinació lineal de les successions ${\displaystyle (\rho ^{n}\cos(n\theta ))_{n\in \mathbb {N} }}$ i ${\displaystyle (\rho ^{n}\sin(n\theta ))_{n\in \mathbb {N} }}$.

Successió recurrent d'ordre p

Subespai vectorial de dimensió p

Si s'anomena ${\displaystyle (R_{p})}$ la relació de recurrència:

per a tot enter n, ${\displaystyle u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}}$

i si s'anomena ${\displaystyle E_{R_{p}}}$, el conjunt de les successions amb valors a K i que verifiquen ${\displaystyle (R_{p})}$, es demostra que ${\displaystyle 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 ${\displaystyle E_{R_{p}}}$ i l'espai vectorial ${\displaystyle K^{p}\,}$: a cada successió (u ) de ${\displaystyle E_{R_{p}}}$, s'associa el p_uplet ${\displaystyle (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 ${\displaystyle (R_{p})}$, llavors el conjunt ${\displaystyle 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 ${\displaystyle K^{p}}$. A cada successió ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ s'associa la successió ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$ tal que

${\displaystyle U_{n}=(u_{n},u_{n+1},\cdots ,u_{n+p-1})}$

La relació de recurrència sobre ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ indueix una relació de recurrència sobre ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$

${\displaystyle U_{n+1}=AU_{n}}$

on

${\displaystyle 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

${\displaystyle U_{n}=A^{n}U_{0}}$

Llavors el problema sembla resolt. Però l'autèntica dificultat consisteix en calcular ${\displaystyle A^{n}}$... Es prefereix determinar més aviat una base de ${\displaystyle E_{R_{p}}}$.

Cerca d'una base

El polinomi característic de la matriu A és ${\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}}$. No és per atzar si es troba per caracteritzar les successions ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ que verifiquen ${\displaystyle R_{p}}$.

Es nota f la transformació lineal que, a una successió ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ associa la successió ${\displaystyle v=(v_{n})_{n\in \mathbb {N} }}$ definida per ${\displaystyle v_{n}=u_{n+1}}$. La condició u verifica ${\displaystyle R_{p}}$ s'ha traduït llavors per P(f)(u) = 0. El conjunt ${\displaystyle 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 ${\displaystyle K=\mathbb {C} }$), existeixen k arrels ${\displaystyle r_{1},r_{2},\cdots ,r_{k}}$ i k exponents ${\displaystyle \alpha _{1},\alpha _{2},\cdots ,\alpha _{k}}$ tals que ${\displaystyle P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}}$. El nucli de P(f) és llavors la suma directa dels nuclis dels ${\displaystyle (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 ${\displaystyle E_{R_{p}}}$.

Es pot demostrar que tota successió de terme general ${\displaystyle Q(n)r_{i}^{n}}$ és un element del nucli de ${\displaystyle (f-r_{i}Id)^{\alpha _{i}}}$ per poc que el grau de Q sigui inferior estrictament a ${\displaystyle \alpha _{i}}$. Aquesta demostració es fa per recurrència sobre ${\displaystyle \alpha _{i}}$. Com que les successions ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, per a j = 0 a ${\displaystyle \alpha _{i}-1}$ formen una familia lliure de ${\displaystyle \alpha _{i}}$ elements, la família de totes les successions ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, per a j = 0 a ${\displaystyle \alpha _{i}-1}$ i per a i = 1 a k formen una família lliure de ${\displaystyle \alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p}$ elements de ${\displaystyle E_{R_{p}}}$ (de dimensió p) per tant una base de ${\displaystyle E_{R_{p}}}$. Els elements de ${\displaystyle E_{R_{p}}}$ són per tant sumes de successions el terme general de les quals és ${\displaystyle Q(n)r_{i}^{n}}$ amb grau de Q estrictament inferior a ${\displaystyle \alpha _{i}}$.

Tornada a la recurrència d'ordre 2

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

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