# Linear recursion with coefficients depending on n

I am searching a way to solve a recursive definition for a sequence in the following form:

$a_n = c_{n-1}\cdot a_{n-1} + b_{n-1}$

So I'd like to have an explicit form of $a_n$ depending only on $c_i$ and $b_i$, but not on $a_n$. I know how to solve linear recursions, but the coefficients are not constant here. Or are there no well-known solutions for this case?

-

As it is, the problem seems a bit too general (any sequence satisfies many such recursions). So while you can express $a_n$ is terms of the $b_i$ and $c_i$, it's not a simple expression in general. Indeed if you set $C_n = \prod_{i = 0}^{n} c_i$, then you can express $a_n$ as
$$a_{n+1} = C_n \, \left(a_0 + \sum_{k = 0}^n \frac{b_k}{C_k}\right)$$
But unless you have specific sequences $(b_n)_{n \ge 0}$ and $(c_n)_{n \ge 0}$, I doubt you can do much better than that.
Well also if have specefic $(b_n)_{n≥0}$ and $(c_n)_{n≥0}$, it might be really difficult to find the solution if I dont' have the right idea. I was wondering if there is something like a characteristic polynomial for this case. – lumbric Nov 12 '11 at 15:10
My point is that since any sequence satisfies such a recursion, it would be hopeless to expect a general method to always give a simple expression (that would imply that any sequence has a simple expression). However, if $(b_n)$ and $(c_n)$ are such that you can find a simple expression for the $C_i$ and the series $\sum \frac{b_i}{C_i}$, then you get a simple expression for $a_n$. I don't know if that helps. – Joel Cohen Nov 12 '11 at 15:22
In a nutshell : there is no general method, but there are many methods and tricks in some specific cases depending on $(b_n)$ and $(c_n)$. For example in some cases, we can use generating functions (en.wikipedia.org/wiki/Generating_function) to derive a formula. – Joel Cohen Nov 12 '11 at 15:36