Resolver un conjunto de relaciones de recurrencia

Question

Tengo las 7 siguientes relaciones de recencia:

$A_n = B_{n-1} + C_{n-1}$

$B_n = A_n + C_{n-1}$

$C_n = B_n + C_{n-1}$

$D_n = E_{n-1} + G_{n-1}$

$E_n = D_n + F_{n-1}$

$F_n = G_n + C_n$

$G_n = E_n + F_{n-1}$

que me gustaría resolver, con el objetivo de encontrar eventualmente una forma explícita de $E_n$ . Empecé por mirar sólo $A_n$ , $B_n$ y $C_n$ y encontró una fórmula para $A_n$ .

$A_n = 1/3 \sqrt{3} (2+ \sqrt{3})^n - 1/3 \sqrt{3} (2 - \sqrt{3})^n$

pero parece que no puedo encontrar el truco correcto esta vez.

Answer 1

Sustituir y eliminar. Ya sabes cómo resolver una recurrencia sobre una función; elimina funciones del sistema hasta llegar a una sola, sustituyendo una función por otra.

Por ejemplo, sustituya $B_{n-1}$ en la definición de $C_n$ para conseguir $$C_n = A_{n-1} + C_{n-2} + C_{n-1}.$$ $B$ se ha eliminado, y estamos un paso más cerca de tener una ecuación que implique sólo $C$ .

Mediante una inspección, $A$ , $B$ y $C$ se definen mutuamente, y por separado $D$ , $E$ , $F$ , $G$ se definen mutuamente, excepto $C$ . Así que resuelve para $C$ primero, utilizando $A$ y $B$ y luego continuar con sólo $D$ , $E$ , $F$ , $G$ .

Esto es muy similar a la eliminación gaussiana, pero hay que lidiar con los subíndices adicionales en $C_{n-1}$ , $C_{n-2}$ etc.

Answer 2

Esto es lo que yo haría:

dejar $A(z) = \sum_{n=0}^\infty A_n z^n$ sea la ``función generadora'' de $A_n$ . Definir $B(z), C(z)$ .

Entonces multiplica la recurrencia $A_n = B_{n-1} + C_{n-1}$ por $z^n$ para conseguir

$$ A_n z^n = B_{n-1} z^n + C_{n-1} z^n $$

y sumar sobre $z^n$ para conseguir

$$ \sum_{n=1}^\infty A_n z^n = \sum_{n=1}^\infty B_{n-1} z^n + \sum_{n=1}^\infty C_{n-1} z^n. $$

El lado izquierdo es $A(z) - A_0$ y el tamaño de la derecha es $z B(z) + z C(z)$ para que puedas obtener $A(z) - A_0 = zB(z) + zC(z)$ . Observe que tuve que escribir $A(z) - A_0$ porque no ha proporcionado las condiciones iniciales.

Puedes hacer lo mismo con la segunda y la tercera ecuación y resolver el sistema resultante de tres en tres, que no debería ser demasiado difícil. Esto te dará $A(z)$ . Ahora sólo hay que encontrar los coeficientes en $A(z)$ ; puede hacerlo escribiendo $A(z)$ en términos de fracciones parciales. Para un ejemplo escrito de esto, véase la sección 1.3 de Generación de funcionalidades por Wilf. (El enlace lleva al texto completo, disponible en línea).

Answer 3

Escribe el sistema en forma de matriz. A continuación, intenta diagonalizar la matriz.

Answer 4

Escribe sin sustracciones en los índices (me gustan las letras lovercase para los miembros de las secuencias, por favor, tened paciencia): \begin{align} a_{n + 1} &= b_n + c_n \\ b_{n + 1} &= a_{n + 1} + c_n \\ c_{n + 1} &= b_{n + 1} + c_n \\ d_{n + 1} &= e_n + g_n \\ e_{n + 1} &= d_{n + 1} + f_n \\ f_n &= g_n + c_n \\ g_{n + 1} &= e_{n + 1} + f_n \end{align} Definir una serie de funciones generadoras como $A(z) = \sum_{n \ge 0} a_n z^n$ multiplique cada recurrencia por $z^n$ y sumar sobre $n \ge 0$ , entonces reconoce, por ejemplo $$ \sum_{n \ge 0} a_{n + 1} z^n = \frac{A(z) - a_0}{z} $$ Esto establece un hermoso sistema lineal de ecuaciones para las funciones generadoras, que su manso sistema de álgebra computacional (en mi caso máxima ) resuelve por ti: $$ E(z) = \frac{e_0 + (c_0 - 7 e_0 + 2 g_0) z + (b_0 + 13 e_0 - 8 g_0) z^2 + (b_0 - c_0 - 3 e_0 + 2g_0) z^3} {(1 - 4 z + z^2)^2} $$ Dividir en fracciones parciales (esto se pone feo, los ceros del denominador son $2 \pm \sqrt{3}$ ) y utilizar el teorema del binomio generalizado para leer los coeficientes.

Answer 5

@utdiscant: ¿Ya lo resolviste? Por favor, muéstrame tus métodos porque también me encontré con un problema similar arriba.
$\left\{\begin{matrix} S_{n}=S_{n-1}+T_{n-1}\\ T_{n-1}=C_{n-3}+D_{n-4}\\ C_{n-3}=E_{n-4}+F_{n-4}\\ E_{n-4}=K_{n-5}+T_{n-5}\\ F_{n-4}=E_{n-7}+D_{n-7}\\ D_{n-7}=H_{n-8}+F_{n-8}\\ H_{n-8}=S_{n-11}+C_{n-11}\\ K_{n-5}=S_{n-7}+C_{n-8} \end{matrix}\right.$
Ahora, estoy intentando resolverlo por la forma matricial pero es muy difícil. En particular, encontrar la matriz generadora y el polinomio característico.