# 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?

## 1 Answer

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
• Yeah you are right of course, but there are helpful methods anyway. Either through generating functions or the characteristic polynomial, see here for example. – lumbric Nov 12 '11 at 15:36
• You were some seconds faster... :) Since there is a genreal method for all linear recursions, I thought maybe this could be extended to this case somehow. But if you say that you don't think so it's also a very useful answere! – lumbric Nov 12 '11 at 15:39
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}