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.