Secuencia lineal recurrente

En matemáticas, se denomina secuencia lineal recurrente de orden p a cualquier sucesión con valores en un campo conmutativo K (por ejemplo ℝ o ℂ; solo se considerará el primer caso en este artículo) definidos para todo ${\displaystyle n\geq n_{0}}$ por una relación de recurrencia lineal de la forma

${\displaystyle \forall n\geq n_{0}\quad u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}}$

donde ${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, ... ${\displaystyle a_{p-1}}$ son p escalares fijos de K (con ${\displaystyle a_{0}}$ no nulo).

Tal secuencia está completamente determinada por los datos de sus primeros términos p y por la relación de recurrencia.

Las secuencias recurrentes lineales de orden 1 son las progresiones geométricas.

El estudio de secuencias lineales recurrentes de orden superior se reduce a un problema de álgebra lineal. La expresión del término general de dicha secuencia es posible siempre que se pueda factorizar un polinomio asociado con él, denominado polinomio característico; el polinomio característico asociado con una secuencia que verifica la relación de recurrencia anterior es:

${\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}=X^{p}-a_{p-1}X^{p-1}-a_{p-2}X^{p-2}-\dots -a_{1}X-a_{0}.}$

Su grado es, por lo tanto, igual al orden de la relación de recurrencia. En particular, en el caso de secuencias de orden 2, el polinomio es de grado 2, y por lo tanto, puede factorizarse utilizando el cálculo de su discriminante. En consecuencia, el término general de secuencias lineales recurrentes de orden 2 puede expresarse utilizando solo los dos primeros términos, algunos valores constantes, algunas operaciones elementales de aritmética (suma, resta, multiplicación, exponencial) y el seno y coseno (si el cuerpo escalar es el cuerpo real). Una de estas secuencias es la famosa sucesión de Fibonacci, que puede expresarse a partir de potencias que involucran la proporción áurea.

Las secuencias recurrentes lineales de orden 1 son las progresiones geométricas.

Si la relación de recurrencia es ${\displaystyle u_{n+1}=qu_{n}}$, el término general es ${\displaystyle u_{n}=u_{n_{0}}q^{n-n_{0}}}$.

Si a y b son dos escalares fijos de K, con b distinto de cero, la relación de recurrencia es

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

Los escalares r tales que la secuencia ${\displaystyle (r^{n})_{n\in \mathbb {N} }}$ se verifican en (R) son las soluciones de la ecuación cuadrática ${\displaystyle r^{2}-ar-b=0}$ . El polinomio ${\displaystyle X^{2}-aX-b}$ entonces se llama el polinomio característico de la secuencia. Su discriminante es ${\displaystyle \Delta =a^{2}+4b}$ . Luego se deberán distinguir varios casos, dependiendo del número de raíces del polinomio característico.

Teorema: El término general de una secuencia de valores en K y verificando (R) es: ${\displaystyle \lambda r_{1}^{n}+\mu r_{2}^{n}}$ si ${\displaystyle r_{1}}$ y ${\displaystyle r_{2}}$ son dos raíces distintas (sobre K) del polinomio ${\displaystyle X^{2}-aX-b}$, ${\displaystyle (\lambda +\mu n)r_{0}^{n}}$ si ${\displaystyle r_{0}}$ es una raíz doble del polinomio ${\displaystyle X^{2}-aX-b}$, con ${\displaystyle \lambda ,\mu }$ parámetros sobre K multiplicando los dos primeros valores de la secuencia.

El caso 1 ocurre por ejemplo si ${\displaystyle K=\mathbb {R} }$ y si el discriminante ${\displaystyle \Delta =a^{2}+4b}$ es estrictamente positivo, o si ${\displaystyle K=\mathbb {C} }$ y ${\displaystyle \Delta \neq 0}$ . Además, si las dos raíces ${\displaystyle r_{1},r_{2}}$ del polinomio ${\displaystyle X^{2}-aX-b}$ son dos complejos conjugados ${\displaystyle \rho \mathrm {e} ^{\mathrm {i} \theta }}$ y ${\displaystyle \rho \mathrm {e} ^{-\mathrm {i} \theta }}$, entonces el término general de dicha secuencia también se escribe:

• ${\displaystyle \rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))}$ con los parámetros A y B en K ( ${\displaystyle =\mathbb {R} }$ o ${\displaystyle \mathbb {C} }$, dependiendo de si se está interesado en secuencias reales o complejas) determinado por los dos primeros valores de la secuencia.

El caso 2 ocurre cuando ${\displaystyle \Delta =0}$ y luego la raíz doble es ${\displaystyle r_{0}={\frac {a}{2}}}$ .

No se pierde nada de la generalidad de la secuencia suponiendo que se define en todos ℕ y no solo en ${\displaystyle n_{0}}$. De hecho, el estudio de una secuencia u que solo se define a partir de ${\displaystyle n_{0}}$ se reduce a la de la secuencia v definida en ℕ por ${\displaystyle v_{n}=u_{n+n_{0}}}$ .

Si una secuencia u verifica que

${\displaystyle \forall n\in \mathbb {N} \quad u_{n+2}=au_{n+1}+bu_{n}\quad (R)}$

entonces puede extenderse a índices negativos y vincularse a las potencias de la matriz

${\displaystyle P:={\begin{pmatrix}a&b\\1&0\end{pmatrix}}}$

(invertible dado que b ≠ 0) por:

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

Esto permite mostrar que para v igual a u o cualquier otra secuencia que satisfaga la misma relación de recurrencia (R) y para todos los enteros i, j, k, l r:^[1]​

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

En particular:

${\displaystyle {\text{si }}u_{0}=0{\text{ entonces}}\quad \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}}$ .

Si se denomina ${\displaystyle (R_{p})}$ la relación de recurrencia:

Para todo entero n, ${\displaystyle u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}}$

y si se denomina ${\displaystyle E_{R_{p}}}$ al conjunto de secuencias de valores en K que satisfacen ${\displaystyle (R_{p})}$, se demuestra que ${\displaystyle E_{R_{p}}}$ es un subespacio vectorial del espacio de secuencias de valores en K. Esto se debe a la linealidad de la relación de recurrencia.

Además, este subespacio es de dimensión p. De hecho, existe un isomorfismo de espacios vectoriales entre ${\displaystyle E_{R_{p}}}$ y ${\displaystyle K^{p}}$: para cada secuencia u ${\displaystyle E_{R_{p}}}$, se asocia la p-tupla ${\displaystyle (u_{0},u_{1},\cdots ,u_{p-1})}$. Entonces es suficiente conocer una familia libre de p secuencias que verifiquen ${\displaystyle (R_{p})}$, todo ${\displaystyle E_{R_{p}}}$ entonces es engendrado por esta familia libre.

La búsqueda del término general y secuencias específicas se lleva a cabo trabajando en ${\displaystyle K^{p}}$. A cada secuencia ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ se le asocia la secuencia ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$ definida por

${\displaystyle U_{n}={\begin{pmatrix}u_{n}\\u_{n+1}\\\vdots \\u_{n+p-1}\end{pmatrix}}.}$

La relación de recurrencia en ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ induce una relación de recurrencia en ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$

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

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

(A es la matriz compañera del polinomio característico de la secuencia).

El término general de la secuencia U se determina entonces por^[2]​

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

El problema parece haber terminado. Pero la verdadera dificultad consiste en calcular ${\displaystyle A^{n}}$ ... Se prefiere determinar una base de ${\displaystyle E_{R_{p}}}$.

El polinomio característico de la matriz A es ${\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}}$. No es casualidad que caracterice a las secuencias ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ que se verifican sobre ${\displaystyle R_{p}}$.

Se denota por f a la transformación lineal que, en una secuencia ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ combina la secuencia ${\displaystyle v=(v_{n})_{n\in \mathbb {N} }}$ definida por ${\displaystyle v_{n}=u_{n+1}}$. La condición "u verifica ${\displaystyle R_{p}}$" se traduce en P(f)(u) = 0. El conjunto ${\displaystyle E_{R_{p}}}$ es por lo tanto el núcleo de P(f). Si el polinomio P se divide en K (que siempre es cierto si K = ℂ), se escribe ${\displaystyle P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}}$ donde ${\displaystyle r_{1},r_{2},\dots ,r_{k}}$ son las raíces de P; y ${\displaystyle \alpha _{1},\alpha _{2},\dots ,\alpha _{k}}$ sus respectivos órdenes de multiplicidad. El núcleo de P(f) es entonces la suma directa de los núcleos de ${\displaystyle (f-r_{i}Id)^{\alpha _{i}}}$. Por lo tanto, es suficiente encontrar una base de cada uno de estos núcleos para determinar una base de ${\displaystyle E_{R_{p}}}$.

Se puede demostrar que cualquier secuencia de términos generales ${\displaystyle Q(n)r_{i}^{n}}$ es elemento del núcleo de ${\displaystyle (f-r_{i}Id)^{\alpha _{i}}}$ siempre y cuando el grado de Q sea estrictamente menor que ${\displaystyle \alpha _{i}}$. Esta demostración se realiza por inducción en ${\displaystyle \alpha _{i}}$. Como las secuencias ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, para j = 0 a ${\displaystyle \alpha _{i}-1}$, forman una partida libre de ${\displaystyle \alpha _{i}}$ elementos,^[3]​ las secuencias ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, para j de 0 a ${\displaystyle \alpha _{i}-1}$ e i de 1 a k, se forma una familia libre de ${\displaystyle \alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p}$ elementos de ${\displaystyle E_{R_{p}}}$ (de dimensión p), que por lo tanto es una base de ${\displaystyle E_{R_{p}}}$. Los elementos de ${\displaystyle E_{R_{p}}}$ son, por lo tanto, sumas de secuencias cuyo término general es ${\displaystyle Q(n)r_{i}^{n}}$ con un grado de Q estrictamente menor que ${\displaystyle \alpha _{i}}$.

Si el polinomio característico se divide en ${\displaystyle (X-r_{1})(X-r_{2})}$ entonces los polinomios Q son de grado 0 y los elementos de ${\displaystyle E_{R_{2}}}$ son secuencias cuyo término general es ${\displaystyle \lambda _{1}r_{1}^{n}+\lambda _{2}r_{2}^{n}}$.

Si el polinomio característico se divide en ${\displaystyle (X-r_{0})^{2}}$ entonces los polinomios Q son de grado 1 y los elementos de ${\displaystyle E_{R_{2}}}$ son secuencias cuyo término general es ${\displaystyle (\lambda _{1}n+\lambda _{2})r_{0}^{n}}$ .

• Generando series de una secuencia lineal recurrente
• Sucesión de Lucas
• Transformación binomial