Ecuaciones de recurrencia lineales con coeficientes constantes

[alexpglez]

Hola a todos. Me apetecía comentarles cómo resolver ecuaciones de recurrencia lineales con coeficientes constantes. Los que saben resolver ecuaciones diferenciales, encontrarán mucha analogía con las lineales.

Una ecuación de recurrencia, es una ecuación, que involucra una sucesión $\{a_n\}_{n=0}^{\infty}$, y se busca encontrar su término general. Es lineal si es del tipo:

$$a_{n+k}=\sum_{j=0}^{k-1}c_j(n)a_{n+j}+f(n) \;\; n\geq 0$$

Con ciertas funciones $f(n)$ y $c_j(n)$. Diremos que es homogénea si $f(n)=0$, y diremos que la ecuación homogénea de una lineal es la misma ecuación pero con $f(n)=0$, por ejemplo, la ecuación homogénea de (NH) sería:

$$a_{n+k}= \sum_{j=0}^{k-1}c_j(n)a_{n+j}$$

Pediremos que cumpla ciertas condiciones de contorno: fijaremos ciertos términos $a_k$. Si en nuestro caso $c_0(n) \not=0 \;\; \forall n$ (requisito que se supondrá en adelante), podemos ver fácilmente que se necesitan exactamente $k$ términos (independientes) para que la solución además de existir, sea única.
Un ejemplo de ello es la sucesión de Fibonacci, que resolveremos después a modo de ejemplo:

$$a_0=0 \;\; a_1=1 \;\;\; a_{n+2}=a_{n+1}+a_n$$

Teorema: Las soluciones de (H), forman un espacio vectorial real de dimensión $k$.
Para demostrar que es un espacio vectorial real, basta ver que si $a_n$ y $b_n$ son soluciones, $c_n=a_n+b_n$ y $d_n=\lambda a_n$ también lo son. Pues trivialmente, la suma y la multiplicación de sucesiones y sucesiones con reales cumplen las propiedades de espacio vectorial, dicho de otro modo: nuestro espacio vectorial es un subespacio del espacio de todas las sucesiones.
Es claramente de dimensión k, pues, como ya hemos comentado, necesitamos k números reales para fijar el resto de términos.
Nota: Si suponemos que los términos y coeficientes puedan ser complejos, tenemos un espacio vectorial complejo de dimensión k. La demostración cambia en el anterior argumento, ahora necesitamos k números complejos para determinar el resto. Aunque trabajemos con sucesiones reales, será imprescindible considerar que puedan ser complejas.

Teorema: Las soluciones de (NH) forman un espacio afín de dimensión $k$, con espacio vectorial base el del anterior teorema.
Sólo hay que ver que dada una solución de (H) y una solución de (NH), la suma es una solución de (NH).

Esto que es puramente teórico, en realidad es muy práctico. Para resolver (NH), necesitamos encontrar una solución particular de (NH) $a_n^p$, y ${u^1_n,...,u^k_n}$, $k$ soluciones linealmente independientes de (H), entonces toda solución será:

$$a_n=a_n^p+\sum_{j=1}^k \lambda_j u_n^{j}$$

Y fijados los valores de $k$ términos, podemos determinar los $\lambda_i$.

Aunque simplifique muchísimo este procedimiento, en la práctica es muy complicado resolver (NH), salvo que los coeficientes sean constantes. Así pues, consideremos constantes los coeficientes $c_j(n)=c_j \;\; c_0\not=0$.

Ecuaciones con coeficientes constantes para (H):
1) Probamos con soluciones del tipo $a_n=r^n$, sustituyendo en (H):

$$r^{n+k}=\sum_{j=0}^{k-1}c_jr^{n+j}$$

Y dividiendo a ambos lados por $r^n$ ($r\not=0$ pues si fuese 0 y tomando $n=0$, $0=c_0 \not=0$) tenemos la siguiente ecuación algebraica:

$$r^{k}=\sum_{j=0}^{k-1}c_jr^{j}$$

Luego por cada raíz distinta tenemos una solución. Si encontramos $k$ raíces, ya tenemos solucionada la ecuación. En caso contrario tenemos los siguientes pasos.

2) Raíces complejas: ¡Qué no cunda el pánico! Como hemos comentado, si los coeficientes y las condiciones de contorno son reales, las soluciones van a ser reales, los complejos sólo son un truco útil, si abusamos de este truco, ¡es necesario considerar que el espacio de soluciones pueda ser complejo!.
Sin embargo, las soluciones vienen a pares: si una solución compleja $z$ aparece, también es solución su conjugada $z^*$.
Para quien no lo supiera todavía y no me crea, esto es muy fácil de demostrar. Si $z$ es raíz:

$$z^k=\sum_{j=0}^{k-1}c_jz^j$$

Entonces como los coeficientes son reales, $c_j^*=c_j$, tomando el complejo conjugado a ambos lados de la igualdad anterior:

$$(z^*)^k=(z^k)^*=(\sum_{j=0}^{k-1}c_jz^j)^*=\sum_{j=0}^{k-1}c_j^*(z^*)^j=\sum_{j=0}^{k-1}c_j(z^*)^j$$

Luego $z^*$ es raíz.
Si aparece una solución compleja, podemos hacer una descomposición polar $z=re^{i\theta}$, y las soluciones correspondientes serán $u_1=z^n=r^n e^{i n \theta} \;\; u_2=(z^*)^n=r^n e^{-in\theta}$. Pero podemos tomar también las soluciones reales:

$$u'_1=\frac{u_1+u_2}{2}=Re[u_1]=r^n cos(n\theta) \;\; u'_2=\frac{u_1-u_2}{2i}=Im[u_1]=r^n sin(n\theta)$$

Si uno se acuerda de este último truco, añade las soluciones sin más y trabaja con reales. Si uno no se acuerda, tiene que, o bien recordarlo, o bien trabajar con complejos.

3) Raíces múltiples (reales o complejas):
En el caso de que una raíz $r$ tenga multiplicidad $m$. Se puede comprobar que $\{ r^n, n r^n,n^2 r^n,..., n^m r^n \}$ son soluciones (independientes de la ecuación), (al igual que pasaba con las ecuaciones diferenciales lineales).
Si es la raíz es compleja $z=r e^{i\theta}$ y tiene multiplicidad $m$, entonces $z^*$ tiene su misma multiplicidad. Se realiza el paso 2 al conjunto de soluciones. Las soluciones reales serían en este caso $\{r^n cos(n\theta),..., n^m r^n cos(n \theta),r^n sin(n\theta),..., n^m r^n sin(n \theta) \}$.


Solución particular para (NH):
En ciertos casos podemos dar con una solución, analizaremos sólo un caso:
Si $f(n)=p(n)g^n$ con algún polinomio $p(n)$. Podemos probar con $a_n=p^*(n) g^n$ con $p^*(n)$ un polinomio de grado mayor o igual que $p(n)$. Probaremos con el polinomio de mínimo grado posible, e iremos subiendo el grado.

Observación: si $f(n)=f_1(n)+f_2(n)$, busquemos dos soluciones particulares a otras dos ecuaciones, $a_n$ para el problema con $f(n)=f_1(n)$ y $b_n$ para el problema con $f(n)=f_2(n)$. Entonces $a_n+b_n$ será una solución particular para el caso inicial ($f(n)=f_1(n)+f_2(n)$). Esto es fácil de ver.
Esta observación nos permite solucionar algunos casos más.


Ejemplos:
1) Sucesión de Fibonacci:

$$a_0=0 \;\; a_1=1 \;\;\; a_{n+2}=a_{n+1}+a_n$$

Probando con $r^n$, tenemos que:

$$r^2=r+1 \;\;\; r=\frac{1\pm\sqrt{5}}{2}=\varphi,\; 1-\varphi$$

Luego el término general será de la forma:

$$a_n=A\varphi^n+B(1-\varphi)^n$$

Y sustituyendo en 0 y 1, se obtiene que $A=-B=\frac{1}{\sqrt{5}}$:

$$a_n=\frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}}$$

¡¡Ya sabéis porque en la sucesión de Fibonacci se habla del número áureo!!

2) Ejemplo no homogéneo

$$a_{n+2}=3a_{n+1}-2a_n+2^n$$

Ya sabemos bucar la solución a la homogénea, centrémonos en buscar una solución particular. Probemos con $a_n=A 2^n$:

$$A2^{n+2}=3A2^{n+1}-2A2^n+2^n$$

$$A(2^2-3\cdot 2+2)=1$$

$$0=1$$

Luego no puede valer como solución. Podríamos anticiparnos a ello porque $2$ es una raíz.

Probemos con $a_n=An2^n$, (hay que tener un poco de picardía para no probar con $(An+B)2^n$, veríamos que $B$ podría ser cualquier valor...):

$$A(n+2)2^{n+2}=3A(n+1) 2^{n+1}-2An2^n+2^n$$

$$A(n+2)4=6A(n+1)-2An+1$$

$$4An+8=4An+6A+1 \;\;\;\; A=\frac{7}{6}$$

Luego la solución general será (raíces $2$ y $1$):

$$a_n=C_1+C_22^n+\frac{7}{6}n2^n$$

Termino contando un truco matricial para resolver recurrencias homogéneas. Por ejemplo, la ecuación de Fibonacci se puede escribir como:

$$<br /> \begin{pmatrix}<br /> a_{n+1} \\<br /> a_{n+2}<br /> \end{pmatrix}<br /> =<br /> \begin{pmatrix}<br /> 0 & 1 \\<br /> 1 & 1<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> a_{n} \\<br /> a_{n+1}<br /> \end{pmatrix}$$

Se ve entonces que:

$$<br /> \begin{pmatrix}<br /> a_{n} \\<br /> a_{n+1}<br /> \end{pmatrix}<br /> =<br /> \begin{pmatrix}<br /> 0 & 1 \\<br /> 1 & 1<br /> \end{pmatrix}^n<br /> \begin{pmatrix}<br /> a_0 \\<br /> a_1<br /> \end{pmatrix}<br /> =<br /> \begin{pmatrix}<br /> 0 & 1 \\<br /> 1 & 1<br /> \end{pmatrix}^n<br /> \begin{pmatrix}<br /> 0 \\<br /> 1<br /> \end{pmatrix}$$

Y el problema consiste en encontrar la potencia n-ésima. La matriz tiene autovalores $\varphi, \; 1-\varphi$, esto es suficiente para comprobar que da el mismo resultado. Toda ecuación de recurrencia lineal homogénea se puede escribir matricialmente como la anterior.

Saludos