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.

  • $\begingroup$ 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. $\endgroup$ – lumbric Nov 12 '11 at 15:10
  • $\begingroup$ 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. $\endgroup$ – Joel Cohen Nov 12 '11 at 15:22
  • $\begingroup$ 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. $\endgroup$ – Joel Cohen Nov 12 '11 at 15:36
  • $\begingroup$ Yeah you are right of course, but there are helpful methods anyway. Either through generating functions or the characteristic polynomial, see here for example. $\endgroup$ – lumbric Nov 12 '11 at 15:36
  • $\begingroup$ 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! $\endgroup$ – lumbric Nov 12 '11 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.