How would I solve or obtain a closed-form solution for a recurrence relation like $$a_n = f_1(n)a_{n-1} + f_2(n)a_{n-2} + ... + f_k(n)a_{n-k} + g(n)$$ where $f_1, f_2, ..., f_k, g$ are polynomials and $\left \{a_n\right \}$ is my recursively defined series? Perhaps it would be simpler to solve $a_n = f(n)a_{n-1} + g(n)$?

I tried solving a simple example, like $a_n = na_{n-1} + 2n + 3$ with the techniques I have learnt to solve homogeneous and non-homogeneous linear recurrences, but it didn't work out (I got a wrong answer). I think I am going wrong where I guess the form of the homogeneous and non-homogeneous parts: usually we think of the homogeneous and non-homogeneous parts as having a form similar to that given in the recurrence relation (eg. linear non-homogeneous recurrence means linear non-homogeneous solution, etc.)

How do I solve these recurrences? Can they be solved at all, at least for simple cases like the one I tried? Thanks for your attention!

Edit: I tried using Wolfram Alpha to solve a few examples, but the answer comes out looking far from easy. Are there any simple examples which I can try to solve on my own, except for trivial ones like $a_n = na_{n-1}$?


A general way is to use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, set up with no substrations in indices:

$$a_{n + k} = f_1(n) a_{n + k - 1} + \dotsb + f_{k - 1}(n) a_n$$

Multiply by $z^n$, sum over $n \ge 0$, and recognize sums:

$$\sum_{n \ge 0} a_{n + r} z^n = \frac{A(z) - a_0 - a_1 z - \dotsb - a_{r - 1} z^{r - 1}}{z^r}$$ $$\sum_{n \ge 0} n^r a_n z^n = (z \frac{d}{d z})^r A(z)$$

Note here e.g. $(z \frac{d}{d z})^2 = z \frac{d}{d z} (z \frac{d}{d z}) = z \frac{d}{d z} + z^2 \frac{d^2}{d z^2}$.

Using the above on your recurrence will eventually give a differential equation for $A(z)$, solve that one and extract coefficients.


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.