I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form:
$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$
As written, each term requires the knowledge of the previous terms. Is it possible to write down a closed form for $Z_n$? For this particular recurrence, I can write down the result of $Z_n$ but I would be very interested in seeing how one can derive this from the recurrence relation itself. My gut feeling is that a generating function is lurking underneath all this.
Best Answer
Your gut feeling is right, but let me change your $x$s to $a$s to make the answer easier to read. Consider the generating functions
$$Z(x) = \sum_{n \ge 0} Z_n x^n$$ $$A(x) = \sum_{n \ge 1} a_n x^n.$$
Then the recurrence relation you have written down is equivalent to
$$Z(x) = Z(x) A(x) + 1$$
which gives
$$Z(x) = \frac{1}{1 - A(x)}.$$
So if you know the generating function $A(x)$ in closed form, you then know the generating function $Z(x)$ in closed form. This is one of the most basic manipulations to do with generating functions, and techniques like this are thoroughly covered in, for example, Wilf's generatingfunctionology.