Solving recurrence relations that involve all previous terms

Question

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.

Answer 1

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.

Answer 2

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.