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.


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.