La solución de relaciones de recurrencia que involucrar a todos los anteriores términos

Question

No estoy seguro de si esta correcto recurance relación per se , pero yo estaría interesado en la metodología en la solución de la recurrencia de la relación de la siguiente forma:

$Z_0 = 1$

$Z_1 = x_1$

$Z_2 = x_1Z_1 + x_2 = x_1^2 + x_2$

$Z_3 = x_1Z_2 + x_2Z_1 + x_3 = x_1^3 + x_1x_2 + x_1x_2 + x_3$

$Z_n = x_1 Z_{n-1} + x_2 Z_{n-2} + ... + x_n Z_0$

Como está escrito, cada término requiere el conocimiento de los anteriores términos. Es posible anotar una forma cerrada para $Z_n$? Para este particular, la recurrencia, puedo escribir el resultado de $Z_n$, pero yo estaría muy interesado en ver cómo se puede derivar de este a partir de la recurrencia de la relación en sí. Mi sensación es que una generación de función está al acecho debajo de todo esto.

Answer 1

Su corazonada es correcta, pero me voy a cambiar a su $x$s a $a$s para que la respuesta más fácil de leer. Considere la posibilidad de la generación de funciones

$$Z(x) = \sum_{n \ge 0} Z_n x^n$$ $$A(x) = \sum_{n \ge 1} a_n x^n.$$

A continuación, la recurrencia de la relación que usted ha escrito es equivalente a

$$Z(x) = Z(x) A(x) + 1$$

lo que da

$$Z(x) = \frac{1}{1 - A(x)}.$$

Así que si usted sabe la generación de la función $A(x)$ en forma cerrada, entonces usted sabe la generación de la función $Z(x)$ en forma cerrada. Este es uno de los más básicos manipulaciones que ver con la generación de funciones y técnicas de este tipo son completamente cubierto en, por ejemplo, Wilf del generatingfunctionology.

Answer 2

Para responder a la pregunta de carácter general en el título ("la solución de relaciones de recurrencia que involucrar a todos los anteriores términos"), tales relaciones puede ser pensado como una ruta de acceso o historia dependiente de cálculos y se intenta sustituir por su equivalente dependiente del estado (Markovian), los cálculos que retener una cantidad finita de información de estado y mantener transformar el estado, pero no recuerdo ninguna información adicional.

Por ejemplo, si la recurrencia es

$S_n = S_0 + S_1 + \dots S_{n-1}$

esto es equivalente a, por $n>1$,$S_n = S_{n-1} + S_{n-1} = 2S_{n-1}$, y recordando el término anterior es suficiente para reproducir la recurrencia según se expresa duplicando (después de los dos primeros términos).

En el ejemplo de la pregunta es también una iteración de una sola transformación, pero en un infinito-dimensional espacio de estado.