# 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
– Joel Cohen Nov 12 '11 at 15:36
– 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
show 1 more comment
{"extraction_info": {"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": 19, "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}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9585433602333069, "perplexity_flag": "head"}