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.

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 ${\displaystyle u_{n+1}=qu_{n}}$ , el término general es ${\displaystyle 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

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

Identidades notables

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

Secuencia de orden recurrente p

Subespacio vectorial de dimensión p

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.

Término general

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

Determinación de una base

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

Vuelta a la recurrencia de orden 2

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

Referencias

1. Robert C. Johnson (2009). . Université de Durham (en inglés). p. 40. Archivado desde el original el 30 de noviembre de 2020. Consultado el 5 de enero de 2020.  (A.10).
2. Jean-Marie Monier (2008). Algèbre et géométrie PC-PSI-PT. Dunod. p. 125. 
3. En réalité, ce résultat n'est vrai que si ${\displaystyle r_{i}\neq 0}$ , mais le cas d'une racine nulle se traite aisément par décalage d'indice.

Artículos relacionados

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

•   Datos: Q23835453