Given $a_n = b_{n}a_{n-1} + a_{n-2}$
with starting conditions: $a_0 = 0,\ a_1 = 1$
I need the explicit form of $a_n$.
$b_n$ are known. For example, let's say $[b_2,b_3,b_4,b_5] = [1,2,3,1]$.
The first few terms of the sequence are: $0,\ 1,\ b_2,\ b_3b_2+1,\ b_4(b_3b_2+1)+b_2,\ …$
For the simpler case where $a_{n-1}$ is always multiplied by the same $b$,
$a_n = ba_{n-1} + a_{n-2}$,
the solution is known. It can be found by guessing $a_n=r^n$ and solving the resultant characteristic equation.
Here's how I tried to solve it:
I know the solution to a geometric sequence $a_n = ba_{n-1}$ is
$a_n = a_0b^n$
And I reasoned if we instead have $a_n = b_na_{n-1}$ it becomes
$a_n = a_0\prod^n_1b_n$
So, I thought maybe I should follow the logic used to solve $a_n = ba_{n-1} + a_{n-2}$, but instead of guessing $a_n=r^n$, trying
$a_n=\prod^n_1r_i = r_1\cdot r_2\cdot\ …\ \cdot r_n$
Plugging this into the recursion relation $a_n = b_{n}a_{n-1} + a_{n-2}$ gives
$\prod^n_1r_i = b_{n}\prod^{n-1}_1r_i + \prod^{n-2}_1r_i $
$\Rightarrow (r_{n}r_{n-1} – b_{n}r_{n-1} – 1)\prod^{n-2}_1r_i = 0$
I think because $a_{n-2}\ne 0$ in general, this implies
${r_{n}r_{n-1} – b_{n}r_{n-1} – 1\ =\ 0}\ $
This is where I get stuck. Instead of a solution for $r_n$, I have a recurrence relation.
$r_n = r_{n-1}^{-1} + b_n$
I'm not sure what the base value $r_1$ would be. Also, I expect to find two possible answers for $r_n$, so that $a_n$ would be a linear combination of those, with coefficients determined by "$a_0 = 0,\ a_1 = 1$".
It occurred to me that if I had another equation relating $r_n$ and $r_{n-1}$, two solutions could be found. For instance, if I had $r_n = r_{n-1}$, I could substitute that in and solve $r_n = r_{n}^{-1} + b_n$, a quadratic with two solutions for $r_n$. However, I don't have that equation, and it can't be true because $b_{n}\ne b_{n-1}$ in general. It's as if I'm missing a vital equation, and I don't know where to find it.
I also tried the telescoping technique:
The LHS of $a_n – a_{n-2} = b_{n}a_{n-1}$ has a lot of cancelling terms when all added up.
$\sum_2^n(a_i – a_{i-2}) = a_2 – a_0 + a_3 – a_1 + a_4 – a_2 + a_5 – a_3\ +\ …\ +\ a_{n-1} – a_{n-3} + a_n – a_{n-2}$
$\Rightarrow – a_0 – a_1 + a_{n-1} + a_n = \sum_2^nb_{i}a_{i-1}$
$\Rightarrow a_n = a_0 + (b_2 + 1)a_1 + \sum_3^{n-1}b_{i}a_{i-1} + (b_n – 1)a_{n-1}$
But even if I've done this correctly, it's not a win because now I have a formula in terms of all preceding $a_n$s instead of just the previous two.
I'm aware that any solution for $a_n$ would have in it some combination of all previous $b_n$s. That's fine, because they are known. Has this problem already been solved? Is it possible to solve, and if not why not?
Best Answer
The recurrence can be written in matrix form as:
$$ A_n = \begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} b_n & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} a_{n-1} \\ a_{n-2} \end{pmatrix} = B_n \cdot A_{n-1} \quad\quad \text{with}\;\; A_1 = \begin{pmatrix} a_{1} \\ a_{0} \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$
Then, telescoping:
$$ A_n = B_n \cdot A_{n-1} = B_n \cdot B_{n-1} \cdot A_{n-2} = \dots = B_n \cdot B_{n-1} \cdots B_2 \cdot A_1 = P_n \cdot A_1 $$
The product $\,P_n = \prod_{k=2}^n B_k\,$ can be calculated recursively, and a "more closed" form may exist for particular sequences $\,b_n\,$.