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\ge n_0$

por una relación de recurrencia lineal de la forma

$\mathrm{\forall }n\ge n_0{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}=q{u}_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}=a{u}_{n+1}+b{u}_n(R).$

Los escalares r tales que la secuencia $(r^n{)}_{n\in \mathbb{N}}$ se verifican en Plantilla:Math 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 $\mathrm{\Delta }=a^2+4b$ . Luego se deberán distinguir varios casos, dependiendo del número de raíces del polinomio característico.

El caso 1 ocurre por ejemplo si $K=ℝ$ y si el discriminante $\mathrm{\Delta }=a^2+4b$ es estrictamente positivo, o si $K=ℂ$ y $\mathrm{\Delta }\ne 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 ( $=ℝ$ o $ℂ$, 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 $\mathrm{\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 Plantilla:Math que solo se define a partir de $n_0$ se reduce a la de la secuencia Plantilla:Math definida en ℕ por $v_n=u_{n+n_0}$ .

Identidades notables

Si una secuencia Plantilla:Math verifica que

$\mathrm{\forall }n\in \mathbb{N}{u}_{n+2}=a{u}_{n+1}+b{u}_n(R)$

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

$P:=\left(\begin{array}{cc}a& b\\ 1& 0\end{array}\right)$

(invertible dado que Plantilla:Math) por:

$\mathrm{\forall }n\in \mathbb{Z}\left(\begin{array}{c}{u}_{n+1}\\ u_n\end{array}\right)=P^n\left(\begin{array}{c}{u}_1\\ u_0\end{array}\right)$ .

Esto permite mostrar que para Plantilla:Math igual a Plantilla:Math o cualquier otra secuencia que satisfaga la misma relación de recurrencia Plantilla:Math y para todos los enteros Plantilla:Math, Plantilla:Math, Plantilla:Math, Plantilla:Math Plantilla:Math:

$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}\mathrm{\forall }m,n,r\in \mathbb{Z}{u}_n{v}_{m+r}-u_r{v}_{m+n}=(-b{)}^r{u}_{n-r}{v}_m$ .

Secuencia de orden recurrente Plantilla:Math

Subespacio vectorial de dimensión Plantilla:Math

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 Plantilla:Math $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=\left(\begin{array}{c}{u}_n\\ u_{n+1}\\ ⋮\\ u_{n+p-1}\end{array}\right).$

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}=A{U}_n$ donde

$A=\left(\begin{array}{ccccc}0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& \ddots & \ddots & \cdots & ⋮\\ 0& \cdots & \cdots & 0& 1\\ a_0& a_1& \cdots & \cdots & a_{p-1}\end{array}\right)$

(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 "Plantilla:Math verifica $R_p$" se traduce en P(f)(Plantilla:Math) = 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$ .

Artículos relacionados

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