# 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 $n\geq n_{0}$ por una relación de recurrencia lineal de la forma
$\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 $a_{0}$, $a_{1}$, ... $a_{p-1}$ son p escalares fijos de K (con $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:
    $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.

## Secuencia lineal recurrente de orden 1

Las secuencias recurrentes lineales de orden 1 son las progresiones geométricas.
Si la relación de recurrencia es $u_{n+1}=qu_{n}$, el término general es $u_{n}=u_{n_{0}}q^{n-n_{0}}$.

## Secuencia lineal recurrente de orden 2

Si a y b son dos escalares fijos de K, con b distinto de cero, la relación de recurrencia es
    $u_{n+2}=au_{n+1}+bu_{n}\quad (R).$
Los escalares r tales que la secuencia $(r^{n})_{n\in \mathbb {N} }$ se verifican en (R) son las soluciones de la ecuación cuadrática $r^{2}-ar-b=0$ . El polinomio $X^{2}-aX-b$ entonces se llama el polinomio característico de la secuencia. Su discriminante es $\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:
* $\lambda r_{1}^{n}+\mu r_{2}^{n}$ si $r_{1}$ y $r_{2}$ son dos raíces distintas (sobre K) del polinomio $X^{2}-aX-b$,
* $(\lambda +\mu n)r_{0}^{n}$ si $r_{0}$ es una raíz doble del polinomio $X^{2}-aX-b$,
* con $\lambda ,\mu$ parámetros sobre K multiplicando los dos primeros valores de la secuencia.
El caso 1 ocurre por ejemplo si $K=\mathbb {R}$ y si el discriminante $\Delta =a^{2}+4b$ es estrictamente positivo, o si $K=\mathbb {C}$ y $\Delta \neq 0$ . Además, si las dos raíces $r_{1},r_{2}$ del polinomio $X^{2}-aX-b$ son dos complejos conjugados $\rho \mathrm {e} ^{\mathrm {i} \theta }$ y $\rho \mathrm {e} ^{-\mathrm {i} \theta }$, entonces el término general de dicha secuencia también se escribe:
* $\rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))$ con los parámetros A y B en K ( $=\mathbb {R}$ o $\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 $\Delta =0$ y luego la raíz doble es $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 $n_{0}$. De hecho, el estudio de una secuencia u que solo se define a partir de $n_{0}$ se reduce a la de la secuencia v definida en ℕ por $v_{n}=u_{n+n_{0}}$ .

### Identidades notables

Si una secuencia u verifica que
    $\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
    $P:={\begin{pmatrix}a&b\\1&0\end{pmatrix}}$
(invertible dado que b ≠ 0) por:
    $\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:
$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:
${\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}$

## Secuencia de orden recurrente p
### Subespacio vectorial de dimensión p

Si se denomina $(R_{p})$ la relación de recurrencia:
    Para todo entero n, $u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}$
y si se denomina $E_{R_{p}}$ al conjunto de secuencias de valores en K que satisfacen $(R_{p})$, se demuestra que $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 $E_{R_{p}}$ y $K^{p}$: para cada secuencia u $E_{R_{p}}$, se asocia la p-tupla $(u_{0},u_{1},\cdots ,u_{p-1})$. Entonces es suficiente conocer una familia libre de p secuencias que verifiquen $(R_{p})$, todo $E_{R_{p}}$ entonces es engendrado por esta familia libre.

### Término general

La búsqueda del término general y secuencias específicas se lleva a cabo trabajando en $K^{p}$. A cada secuencia $(u_{n})_{n\in \mathbb {N} }$ se le asocia la secuencia $(U_{n})_{n\in \mathbb {N} }$ definida por
    $U_{n}={\begin{pmatrix}u_{n}\\u_{n+1}\\\vdots \\u_{n+p-1}\end{pmatrix}}.$
La relación de recurrencia en $(u_{n})_{n\in \mathbb {N} }$ induce una relación de recurrencia en $(U_{n})_{n\in \mathbb {N} }$
    $U_{n+1}=AU_{n}$ donde
    $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
    $U_{n}=A^{n}U_{0}.$
El problema parece haber terminado. Pero la verdadera dificultad consiste en calcular $A^{n}$ ... Se prefiere determinar una base de $E_{R_{p}}$.

### Determinación de una base

El polinomio característico de la matriz A es $P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}$. No es casualidad que caracterice a las secuencias $u=(u_{n})_{n\in \mathbb {N} }$ que se verifican sobre $R_{p}$.
Se denota por f a la transformación lineal que, en una secuencia $u=(u_{n})_{n\in \mathbb {N} }$ combina la secuencia $v=(v_{n})_{n\in \mathbb {N} }$ definida por $v_{n}=u_{n+1}$. La condición "u verifica $R_{p}$" se traduce en P(f)(u) = 0. El conjunto $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 $P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}$ donde $r_{1},r_{2},\dots ,r_{k}$ son las raíces de P; y $\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 $(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 $E_{R_{p}}$.
Se puede demostrar que cualquier secuencia de términos generales $Q(n)r_{i}^{n}$ es elemento del núcleo de $(f-r_{i}Id)^{\alpha _{i}}$ siempre y cuando el grado de Q sea estrictamente menor que $\alpha _{i}$. Esta demostración se realiza por inducción en $\alpha _{i}$. Como las secuencias $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$, para j = 0 a $\alpha _{i}-1$, forman una partida libre de $\alpha _{i}$ elementos, las secuencias $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$, para j de 0 a $\alpha _{i}-1$ e i de 1 a k, se forma una familia libre de $\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p$ elementos de $E_{R_{p}}$ (de dimensión p), que por lo tanto es una base de $E_{R_{p}}$. Los elementos de $E_{R_{p}}$ son, por lo tanto, sumas de secuencias cuyo término general es $Q(n)r_{i}^{n}$ con un grado de Q estrictamente menor que $\alpha _{i}$.

### Vuelta a la recurrencia de orden 2

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