Encontrar una forma cerrada para una relación de recurrencia $a_n=3a_{n-1}+4a_{n-2}$

Question

Consideremos la secuencia definida por $$\begin{cases} a_0=1\\ a_1=2\\ a_n=3a_{n-1}+4a_{n-2} & \text{if }n\ge 2 \end{cases} .$$ Encuentre una forma cerrada para $a_n$ .

---

He intentado hacer una lista de ejemplos, pero no veo ningún patrón común entre ellos. Todas las soluciones son muy apreciadas.

Answer 1

Para las recurrencias lineales homogéneas de la forma $a_n = \alpha a_{n-1}+\beta a_{n-2}$ mira el polinomio característico asociado:

$$\chi(x)=x^2-\alpha x - \beta$$

En este caso, tenemos el polinomio característico $x^2-3x-4$ que factores como $(x-4)(x+1)$

En el caso de que las raíces sean distintas, digamos $\lambda_1,\lambda_2$ la solución general será de la forma $a_n = c_1 \lambda_1^n + c_2\lambda_2^n$ para algunas constantes $c_1$ y $c_2$ a determinar a partir de las condiciones iniciales.

En el caso de que las dos raíces sean iguales (es decir $\lambda_1=\lambda_2$ ) entonces la solución general será de la forma $a_n = c_1\lambda^n + c_2n\lambda^n$

En nuestro caso, las raíces son $4$ y $-1$ respectivamente por lo que vemos que nuestra solución general será de la forma

$$a_n = c_1 4^n + c_2(-1)^n$$

Ahora, queremos encontrar qué valores de $c_1$ y $c_2$ funcionará para esto. Se nos dice qué $a_0$ y $a_1$ son, así que usando esta información tenemos un sistema de dos ecuaciones y dos incógnitas:

$$\begin{cases}a_0 = c_14^0 + c_2(-1)^0\\ a_1 = c_14^1 + c_2(-1)^1\end{cases}$$

Simplificando:

$$\begin{cases} 1 = c_1+c_2\\ 2=4c_1-c_2\end{cases}$$

Resolviendo sumando primero las dos líneas, tenemos $5c_1=3$ que implica $c_1=\frac{3}{5}$ implicando además que $c_2=\frac{2}{5}$

Esto nos dice que la forma cerrada final es:

$$a_n = \frac{3\cdot 4^n + 2(-1)^n}{5}$$

---

( el método anterior se extiende muy bien también a las recurrencias lineales de orden superior, así como a las formas no homogéneas. la mayoría de los libros de texto sobre el tema tendrán más información )

Answer 2

Esta relación de recurrencia se puede describir con la siguiente matriz: $\operatorname A = \left[\begin{array}{cc} 3 & 4 \\ 1 & 0 \\ \end{array} \right]$

Esto significa que la ecuación $$\operatorname A\left[\begin{array}{cc} a_{n-1} \\ a_{n-2} \\ \end{array} \right] = \left[\begin{array}{cc} 3a_{n-1} + 4 a_{n-2} \\ a_{n-1} \\ \end{array} \right] = \left[\begin{array}{cc} a_{n} \\ a_{n-1} \\ \end{array} \right]$$ se mantiene. ¿Por qué es esto hermoso? En primer lugar, por multiplicación repetida tenemos que $$\operatorname A^k\left[\begin{array}{cc} a_{1} \\ a_{0} \\ \end{array} \right] = \left[\begin{array}{cc} a_{k+1} \\ a_{k} \\ \end{array} \right]$$ que le da una forma de calcular el $\mathbb N \ni n$ a término en $O(\log n)$ tiempo, utilizando la exponenciación binaria (matricial). Como el tamaño de la matriz es realmente pequeño, es una forma muy rápida.

Vale, eso está muy bien, pero has pedido una forma cerrada. Bueno, usted puede obtener que a partir de esto también. Digamos que has diagonalizado esta matriz, y has obtenido $\operatorname A = S \Lambda S^{-1}$ . En este caso, $$\operatorname \Lambda = \left[\begin{array}{cc} 4 & 0 \\ 0 & -1 \\ \end{array} \right]\quad \text{and} \quad S = \left[\begin{array}{cc} 4 & 1 \\ 1 & -1 \\ \end{array} \right].$$

Utilizando $\operatorname A^k = S\Lambda^k S^{-1}$ , obtenemos que $$\left[\begin{array}{cc} a_{k+1} \\ a_{k} \\ \end{array} \right] = \operatorname A^k\left[\begin{array}{cc} a_{1} \\ a_{0} \\ \end{array} \right]= S\Lambda^k S^{-1} \left[\begin{array}{cc} a_{1} \\ a_{0} \\ \end{array} \right] = \left[\begin{array}{cc} 4^{k+1} & (-1)^k \\ 4^k & (-1)^{k-1} \\ \end{array} \right] \left[\begin{array}{cc} \frac{3}{5} \\ -\frac{2}{5} \\ \end{array} \right] =\left[\begin{array}{cc} \frac{3}{5} 4^{k+1} + \frac{2}{5} (-1)^{k+1} \\ \frac{3}{5} 4^{k} + \frac{2}{5} (-1)^{k} \\ \end{array} \right].$$ lo que implica $$a_k = \frac{3}{5} 4^{k} + \frac{2}{5} (-1)^{k}.$$

Vale, vale todo esto está muy bien, pero ¿no puedo hacerlo más rápido? Bueno, en este caso, puedes.

Comience por tratar de encontrar $a_n$ en forma de $q^n$ Es decir $$a_n = 3a_{n-1} + 4a_{n-2} \quad \text{becomes}\quad q^n = 3q^{n-1} + 4q^{n-2}$$ dividir por $q^{n-2}$ y obtendrás la ecuación cuadrática $q^2 - 3q - 4 = 0$ . Las raíces de este polinomio son $-1$ y $4$ . Supongamos que $a_n$ debe ser una combinación lineal de los $n$ de estos, es decir $a_n$ tiene la forma de $a_n = a4^n + b(-1)^n$ . Para encontrar $a$ y $b$ podemos usar eso $a_0$ y $a_1$ sustituyendo $n=0,1$ obtenemos $$\begin{align} a + b &= a_0 = 1 \\ 4a - b &= a_1 = 2 \end{align}$$ Si se resuelve esto, se obtiene $a = \frac{3}{5}, b= \frac{2}{5}$ , lo que implica $$a_k = \frac{3}{5} 4^{k} + \frac{2}{5} (-1)^{k}.$$

Si estás familiarizado con el significado de la palabra polinomio característico, entonces te darás cuenta de que los "dos" métodos que he descrito anteriormente están estrechamente relacionados, ya que $k_A(x) = x^2 - 3x - 4$ es el polinomio característico de $\operatorname A$ . Además, calcular sus raíces es lo mismo que calcular los valores propios de $\operatorname A$ . La única gran diferencia es que no hay que saber nada de matrices para hacer el segundo método, que además es más rápido, y la razón por la que funciona está oculta en el primer método.

Unas palabras sobre el cálculo de los grandes poderes de $\operatorname A$ . Esto es más relevante si la matriz tiene un tamaño grande y un polinomio característico igualmente agradable. Digamos que se quiere calcular $A^{10^{10000}}$ y digamos que $A$ es un $m\times m$ con un polinomio característico de $k_A$ , donde $\deg(k_A)$ es pequeño, comparado con $10^{10000}$ . Por el teorema de Cayley-Hamilton, sabemos que $k_A(A) = 0$ .

Así que el bonito truco consiste en calcular $h(x) = x^{10^{10000}} \mod k_A(x)$ primero, y luego $h(A)$ . Esencialmente, dado cualquier polinomio $f(x)$ con el fin de calcular $f(A)$ se puede encontrar el elemento correspondiente $r(x)$ en el ring $R[x]/k_A(x)$ y, a continuación, calcular $r(A)$ utilizando, de nuevo, la exponenciación binaria.

Answer 3

Una pista: $$a_n-4a_{n-1}=-(a_{n-1}-4a_{n-2})$$

Esto indica $b_n=-b_{n-1}$

Resolviendo la ecuación $x^2=ax+b$ , $$a_n-\alpha a_{n-1}=\beta(a_{n-1}-\alpha a_{n-2})$$