Resolver la recursión, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$

Question

Traer los siguientes recursividad relación a una expresión explícita:

$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$ $a_{0} = 0$, $a_1 = 1$, $a_2 = 2$

Todos los ejemplos que he visto fueron con un máximo de 2 pasos hacia atrás ($a_{n-2}$) y pensé que saben cómo resolver esos, pero estoy teniendo un momento difícil tanto con la Generación de la función y el polinomio Característico de los métodos.

La Generación de la función debe comenzar desde $n = 3$, pero ¿qué pasaría con los valores definidos?

Para el polinomio Característico, significa que voy a tener que encontrar las raíces de un polinomio de un grado 3?

Answer 1

Si utiliza el polinomio característico, de hecho, será un cúbicos, pero es un cúbicos que factores muy fácilmente:

$$x^3-3x_2+3x-1=(x-1)^3\;.$$

Si utiliza funciones de generación, tenga en cuenta que usted puede escribir a la recurrencia como

$$a_n=3a_{n-1}-3a_{n-2}+a_{n-3}+8-8[n=0]-7[n=1]-9[n=2]\;,\tag{1}$$

válido para todos los $n\in\Bbb Z$ si hacer la manta de la suposición de que $a_n=0$ todos los $n<0$. Los tres últimos términos son Iverson soportes y están ahí para hacer la recurrencia de rendimiento de la correcta valores iniciales.

Ahora multiplique $(1)$ $x^n$ y suma más de $n\ge 0$:

$$\sum_{n\ge 0}a_nx^n=3\sum_{n\ge 0}a_{n-1}x^n-3\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}a_{n-3}x^n+8\sum_{n\ge 0}x^n-8-7x-9x^2\;.\tag{2}$$

Si la generación de la función es $A(x)$, $(2)$ puede escribirse como

$$A(x)=3xA(x)-3x^2A(x)+x^3A(x)+\frac8{1-x}-8-7x-9x^2\;,$$

que luego se puede resolver por $A(x)$ y resolver en fracciones parciales.

Answer 2

Para ampliar uno de los comentarios, si $A_n$ es una solución de la parte homogénea $$A_n=3A_{n-1}-3A_{n-2}+A_{n-3}$$ and $B_n$ satisfies $$B_n=3B_{n-1}-3B_{n-2}+B_{n-3}+8$$ then $kA_n+B_n$ satisface la original de recurrencia.

El polinomio característico de la parte homogénea es $(x-1)^3$. Me han dado algunas respuestas a preguntas similares en el contenido de entrar en un torpe forma de ¿por qué las siguientes obras de generación de funciones de dar la misma respuesta, y una prueba de sonido - $A_n=(pn^2+qn+r)1^n$ donde $p, q, r$ son arbitrarias, y he enfatizado $1^n (=1)$ porque sería $2^n$ si la generación de la función de un factor de $(x-2)^3$, y sería un cúbicos en $n$ si se $(x-\alpha)^4$ (etc).

La dificultad surge porque la parte no homogénea $8=8\times 1^n$, e $1$ es una solución del polinomio característico, por lo que la obvia función de la prueba de $B_n=constant$ no trabaja. De hecho, debido a $A_n$ implica una ecuación cuadrática, es el siguiente de mayor potencia de la prueba: $B_n=kn^3$ para encontrar el valor de $k$.

Como digo, la generación de funciones de llegar, como otros métodos, si quieres demostrar que el método funciona. Por otro lado, si desea identificar rápidamente una solución, es útil saber que las funciones de prueba. $A_n+B_n$ tiene tres parámetros $p, q, r$ que determinar la secuencia, y estos corresponden a los tres valores de $a_n$ que están obligados a hacer lo mismo. Así que, dados los valores iniciales (o tres valores de $a_m$), es fácil mostrar que la solución es única. Las funciones de prueba y me han sugerido trabajo, por lo que proporcionan la solución.

Trate de hacer esto, debido a que la teoría de todos los bloquea juntos.

Answer 3

Reescribir la expresión para la simplicidad como $$a_ {k + 3} = 3 a_ {k + 2}-3 a_ {k+1} + a_k + 8$$ multiplicar por $z^k$ y suma $k$ para obtener la función generadora $G(z)=\sum_{k \geq 0}a_k z^k$. En LHS obtendrá $$\frac{1}{z^3}\bigg (G (z) - a_0 - a_1 z-z a_2 ^ 2\bigg)$$ en el lado derecho se obtiene $\frac{3}{z}\bigg (G (z)-a_0\bigg)-\frac {3} {z ^ 2} \bigg (G (z) - a_0 - a_1 z\bigg) + G (z) + \frac {8} {1-z}$$ahora hacer el álgebra cuidadosamente para obtener$G(z)$de la LHS y RHS alguna expresión de la forma$\sum_{k=0}^{\infty}\varphi_k z^k$. ¿Se puede manejar desde aquí?