# Recurrence with Polynomial Coefficients of $n$

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.