2
$\begingroup$

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 Answers 1

3

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.

  • 0
    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.2011-11-12
  • 0
    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.2011-11-12
  • 0
    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 (http://en.wikipedia.org/wiki/Generating_function) to derive a formula.2011-11-12
  • 0
    Yeah you are right of course, but there are helpful methods anyway. Either through generating functions or the characteristic polynomial, see [here](http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients) for example.2011-11-12
  • 0
    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!2011-11-12
  • 0
    Sorry, you acutally answered my question completly. I had different expectations and didn't want to see that you are right... ;)2011-11-14