Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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