Solving recurrence relations that involve all previous terms 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.
 A: To answer the general question in the title ("solving recurrence relations that involve all previous terms"), such relations can be thought of as path- or history-dependent calculations and one tries to replace them by equivalent state-dependent (Markovian) calculations that retain a finite amount of state information and keep transforming the state, but not remembering any additional information. 
For example, if the recurrence is
$S_n = S_0 + S_1 + \dots S_{n-1}$     
this is equivalent, for $n>1$,  to $S_n = S_{n-1} + S_{n-1} = 2S_{n-1}$, and remembering the previous term is enough to reproduce the recurrence as iterated doubling (after the first two terms).
The example in the question is also an iteration of a single transformation, but on an unbounded-dimensional state space.
A: 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.
