1

I'm trying to understand if my approach for solving a recurrence relation is flawed, here I give an example.

Given a recurrence relation $r_n = a + b_n r_{n+1}$,

If we're given an initial condition of $r_0 = c_0$ this can be solved allowing us to calculate $r_n$ in closed form, not depending on $r_{n-1}$.

What if we are instead given an initial condition $r_n = c_n$, and I am interested in knowing the first term $r_0$? I can calculate this by working backwards from $r_n$, but is it possible to find a closed form for $r_0$?

abnowack
  • 155
  • 5
  • 1
    You could use your given recurrence relation, rewritten with n-1 for n, and solve for $r_n$ [which will start out on the right but not yet isolated]. Once that is done it becomes possible to use usual methods to go for closed form of $r_0.$ – coffeemath Jan 18 '23 at 09:13
  • @coffeemath Replace $n$ with $n-1$ and solving for $r_n$, I'll have $r_n = (r_{n-1} - a) / b_{n-1}$. I'm having trouble following after this, do we change indexes so to mean "terms before $r_n$"? – abnowack Jan 18 '23 at 09:43
  • What is your closed form in your example? (i.e. your expression of $r_n,$ knowing $r_0$ and $b_0,\dots,b_{n-1}$) – Anne Bauval Jan 18 '23 at 10:18
  • @AnneBauval Using Mathematica I get the following, $r_n = \left( \prod_{i = 0}^{n-1} \frac{1}{b_i} \right) \left( r_0 - \sum_{i = 0}^{n-1} \frac{a}{b_i \prod^i_{j=0} (1 / b_j ) }\right)$ – abnowack Jan 18 '23 at 10:33

1 Answers1

1

$$r_0=b_0\dots b_{n-1}r_n+a\sum_{i=0}^{n-1}\prod_{0\le j<i}b_j.$$ This can be proved either directly from your recurrence relation, or by reversing the formula you gave in the comments.

Anne Bauval
  • 34,650
  • 1
    Thanks. This was clear, I just realized why I've been confused is that I had the $c_1$ constant term that mathematica gives is $r_1 = c_1$, I had in my head that $r_0 = c_1$. Thanks for helping, going through this small example helped me see clearer – abnowack Jan 18 '23 at 11:31