Ecuaciones de Recurrencia

Sea $x_{n+k}=f(x_n,x_n+1,x_n+2,\cdots ,x_n+k-1)$ con conocidos $x_0,x_1,\cdots ,x_{k-1}$. Es un PVI (problema de valor inicial) de orden $k$.

Una función $x$ con dominio en $\mathbb{N}$ es una sucesión $(x:\mathbb{N}\to C)$ habitualmente denotada $x(n)$, aunque para abreviar, se puede definir $x_n\stackrel{\text{def}}{=}x(n)$.

Si $f$ es lineal, la ecuación de recurrencia también es lineal. En esta materia, únicamente trabajaremos con ecuaciones de recurrencia lineales.

Ecuación de Primer Orden

Sea $x_{n+1}=a{x}_n+b$, con $x_0,a,b$ constantes, entonces podemos llegar a una solución de forma artesanal de la forma

$$x_{n+1}=x_0{a}^n+b\frac{a^n-1}{a-1},a\ne 1$$

Podemos llegar a una expresión equivalente, definiendo $x^{\ast }$ como el punto de equilibrio:

$$x_{n+1}=\{\begin{array}{l}(x-x^{\ast })a^n+x^{\ast },x^{\ast }=\frac{b}{1-a},a\ne 1\\ x_0+bn,a=1\end{array}$$

Observamos que se cumple:

• Si $x_0=x^{\ast }$, entonces $x_n=x^{\ast }$ para cualquier $n$.

• El punto de equilibrio es un atractor global si $|a|<1$:

  $$\underset{n\to \inf }{\lim }{x}_n=x^{\ast }$$

• El punto de equilibrio es un repulsor global si $|a|>1$:

  $$\nexists \underset{n\to \inf }{\lim }{x}_n$$

• Si $a=1$, tiene un comportamiento lineal (como se define en la expresión general)

• Si $a=-1$, entonces $x_n$ oscila infinitamente alrededor de $x_{\ast }$

Si $b$ ya no es constante, tendremos $x_{n+1}=a{x}_n+b_n$, en donde encontramos la solución general

$$x_0{a}^n+\sum _{k=0}^{n-1}{a}^k{b}_{n-1-k}$$

Solución General

Sea $a$ constante, entonces la ecuación de recurrencia de la forma

$$x_{n+1}=a{x}_n+b_n$$

Podemos obtener la solución general como suma de solución de la homogénea más una solución particular.

1. Definimos la ecuación homogénea $x_{n+1}-a{x}_n=0$ y la ecuación característica $\lambda -a=0$. De aquí, obtenemos el espectro $\sigma =\{{\lambda }_1=a\}$. Luego, la solución de la homogénea será de la forma

   $$X_{h_n}=C_1{a}^n$$

2. Proponemos una solución particular $x_{p_n}$ cuya forma dependerá de $b_n$.

   1. Si $b_n$ es un polinomio: $x_{p_n}$ será un polinomio del mismo grado si $a\ne 1$, multiplicado por $n$ si $a=1$.
   2. Si $b_n$ es una exponencial del tipo ${\alpha }^n$, se propone otra exponencial del mismo tipo cuando $\alpha \ne \lambda$, multiplicada por $n$ si $\alpha =\lambda$.
   3. Si $b_n$ es una combinación lineal de los casos anteriores, se propone una combinación lineal de las reglas anteriores
   4. Si $b_n$ es un producto de las reglas anteriores, se propone un producto de las reglas anteriores si $\alpha \ne \lambda$, multiplicado por $n$ si $\alpha =\lambda$.

   Para hallar los coeficientes, reemplazamos la solución planeada en la ecuación de recurrencia

3. Hallamos la solución general como suma de ambas

   $$X_n=X_{h_n}+X_{p_n}$$

4. Imponemos la condición inicial para hallar las constantes apropiadas

Ecuación de Segundo Orden, Homogénea

Sea $a,b$ constantes, entonces la ecuación de recurrencia de la forma

$$x_{n+2}+a{x}_{n+1}+b{x}_n=0$$

Podemos obtener la solución general como suma de solución de la homogénea más una solución particular.

1. Definimos la ecuación homogénea $x_{n+2}+a{x}_{n+1}+b{x}_n=0$ y la ecuación característica ${\lambda }^2+a\lambda +b=0$. De aquí, obtenemos el espectro $\sigma =\{{\lambda }_1,{\lambda }_2\}$. Luego, la solución de la homogénea será de la forma:

   1. Si ${\lambda }_1\ne {\lambda }_2\in \mathbb{R}$, entonces proponemos como solución $x_n=C_1{\lambda }_1^n+C_2{\lambda }_2^n$

   2. Si ${\lambda }_1={\lambda }_2\in \mathbb{R}$, entonces proponemos como solución $x_n=C_1{\lambda }_1^n+C_{2}n{\lambda }_1^n$

   3. Si ${\lambda }_1={\overline{\lambda }}_2\in \mathbb{C}$ con ${\lambda }_{1,2}=r{e}^{\pm i\theta }$, entonces proponemos como solución a:

      $x_n=C_1{r}^n\cos (n\theta )+C_2{r}^n\sin (n\theta )$

2. Debido a que es homogénea, únicamente debemos hallar las constantes a partir de la condición inicial.

Ecuación de Orden Superior Homogénea

Si la ecuación de recurrencia es de orden $q$, para la construcción de la solución de la homogénea se utilizan las mismas reglas que para las de orden 2.

Si una raíz es de multiplicidad $m$, entonces se suma un término por cada multiplicidad, cada vez multiplicando por $n$ una vez más.

Ecuación de Orden Superior Completa

Proponemos una solución particular, cuya forma dependerá del término independiente $f_n$.

1. Si $f_n$ es un polinomio de orden $q$, se propone un polinomio de orden $q$ si $1$ no pertenece al espectro, multiplicado por $n$ elevado a su multiplicidad de la raíz.
2. Si $f_n$ es exponencial, se propone otra del mismo tipo si $\alpha$ no pertenece al espectro, multiplicada por $n$ elevado a su multiplicidad si lo hace.
3. Si $f_n$ es una combinación lineal de ambas reglas, se propone una combinación lineal de las propuestas
4. Si $f_n$ es de la forma $a\cos (n\alpha )+b\sin (n\alpha )$, entonces se propone ecuación del mismo tipo si $e^{i\alpha }$ no pertenece al espectro, multiplicada por $n$ elevado a su multiplicidad si lo hace.

Análisis Cualitativo de las Soluciones

Sea la ecuación característica $x_{n+2}+a{x}_{n+1}+b{x}_n=c$, entonces debemos analizar la convergencia de $x_n$ para cualquier condición inicial.

Si ${\lambda }_1\ne {\lambda }_2$ con ${\lambda }_1,{\lambda }_2\ne 1$

La solución particular será $x_{np}=k$. Luego, reemplazando la solución en la ecuación, encontramos que $k=\frac{c}{1+a+b}$. Como $1$ no es raíz de la ecuación característica, sabemos que el denominador nunca podrá valer cero. Debido a que 1 no pertenece al espectro, la solución de la homogénea será $x_{hn}=C_1{\lambda }_1^n+C_2{\lambda }_2^n$ Definimos entonces la solución general, como:

$$x_n=C_1{\lambda }_1^n+C_2{\lambda }_2^n+\frac{c}{1+a+b}$$

Vemos que si las raíces son de módulo mayor a uno, entonces la serie diverge debido a la exponenciación.

$$\underset{n\to \infty }{\lim }{x}_n=\frac{c}{1+a+b},\forall x_0,x_1⟺|{\lambda }_1|,|{\lambda }_2|<1$$ $$\{\begin{array}{l}1+a+b\ne 0\\ a^2\ne 4b\end{array}$$

Si ${\lambda }_1={\lambda }_2=1$

Sabemos que tanto la ecuación de característica como su derivada se anulan en $\lambda =1$. Luego, encontramos que $a=-2$ y $b=1$. Proponemos como solución de la ecuación particular $x_{np}=kn$ debido a que $1$ pertenece al espectro. Sustituyendo en la ecuación de recurrencia, encontramos que $k_1=c/2$. Como conocemos la raíz, definimos, la solución homogénea como $x_{hn}=C_1+C_{2}n$. Definimos como solución general.

$$x_n=C_1+C_{2}n+\frac{c}{2}{n}^2$$

Vemos que el término puede divergir debido al crecimiento lineal dado por la condición inicial $C_2$.

$$\exists x_0,x_1:\nexists \underset{n\to \infty }{\lim }{x}_n$$

Este caso se encuentra cuando:

$$\{\begin{array}{l}a=-2\\ b=1\end{array}$$

Si ${\lambda }_1\ne {\lambda }_2,{\lambda }_1=1$

Nuevamente, tendremos que $1+a+b=0$. Debido a que las raíces no pueden ser complejas, con la fórmula resolvente obtenemos que $a^2>4b$. Debido a que la raíz no es doble, también obtenemos $a\ne -2$. La solución homogénea tendrá la forma $x_{hn}=C_1+C_2{\lambda }_2^n$. Proponemos la solución particular $x_{pn}=k_{1}n$, y a partir de sustituir en la ecuación de recurrencia, obtenemos que $k_1=\frac{c}{2+a}$. Como $a\ne 2$, siempre podremos despejar $k_1$. La solución general entonces será

$$x_n=C_1+C_2{\lambda }_2^n+\frac{c}{2+a}n$$

Vemos que el término únicamente converge si anulamos tanto el crecimiento exponencial como el crecimiento lineal.

$$\underset{n\to \infty }{\lim }{x}_n=C_1,\forall x_0,x_1⟺|{\lambda }_2|<1,c=0$$

Este caso se encuentra cuando:

$$\{\begin{array}{l}1+a+b=0\\ a\ne 2\\ a^2>4b\end{array}$$

Si ${\lambda }_1={\lambda }_2=\lambda \ne 1$

Entonces tendremos que $1+a+b\ne 0$. Proponemos como solución general $x_{hn}=C_1{\lambda }_1^n+C_2{\lambda }_2^n$. Para la solución particular, propondremos (como 1 no pertenece al espectro) $x_{pn}=k_1$. Si sustituimos en la ecuación de recurrencia, obtenemos que $k_1=\frac{c}{1+a+b}$. Sabemos que el denominador no puede valer cero. Definimos entonces la solución general

$$x_n=C_1{\lambda }^n+C_{2}n{\lambda }^n+\frac{c}{1+a+b}$$

Vemos que el término únicamente converge si anulamos el crecimiento exponencial. Como la exponenciación converge más rápido que la linealidad, esto también anula el segundo término.

$$\underset{n\to \infty }{\lim }{x}_n=\frac{c}{1+a+b},\forall x_0,x_1⟺|\lambda |<1$$

Este caso se encuentra cuando:

$$\{\begin{array}{l}1+a+b\ne 0\\ a^2>4b\end{array}$$

Vemos que si los módulos ${\lambda }_1,{\lambda }_2$ son menores a cero, entonces la solución converge siempre (si no tomamos la solución trivial $c=0$).

Espacio de Coeficientes

El espacio de coeficientes consiste en hallar todos los $a,b$ tales que la solución siempre converge. Para hacerlo, podemos ayudarnos de las identidades:

$${\lambda }_1+{\lambda }_2=-a$$ $${\lambda }_1{\lambda }_2=b$$