Is it possible to find the explicit formula for the recurrence relation $a_n = b_{n}a_{n-1} + a_{n-2}$, where $b_{n}$ are known? 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?
 A: 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\,$.
A: Essentially, $a_n$ is the $n$th partial numerator of the continued fraction
$$0+\dfrac{1}{1+\dfrac{1}{b_2+\dfrac{1}{b_3+\cdots}}}\ .$$
There is no known simple formula for $a_n$ in terms of $b_n$.  However, Euler's rule may be of interest.

*

*Write down the string $b_2b_3b_4\cdots b_n$.

*Write down all strings you can obtain by deleting pairs of consecutive letters from this expression.  This includes the original string (deleting no letters).  If $n$ is odd, it is possible to delete all letters, and this expression will be taken to mean $1$.

*Add all the results from the previous step.

Example: $n=4$.  Starting with $b_2b_3b_4$ you get
$$b_2b_3b_4+b_4+b_2\ ,$$
which matches your $a_4$.
Another example: $n=7$.  Starting with $b_2b_3b_4b_5b_6b_7$, you get the strings (red letters are not really there, they are deleted)
$$\displaylines{b_2b_3b_4b_5b_6b_7,\ \color{red}{b_2b_3}b_4b_5b_6b_7,\ b_2\color{red}{b_3b_4}b_5b_6b_7,\ b_2b_3\color{red}{b_4b_5}b_6b_7,\ b_2b_3b_4\color{red}{b_5b_6}b_7,\cr
 b_2b_3b_4b_5\color{red}{b_6b_7},\ \color{red}{b_2b_3}\color{red}{b_4b_5}b_6b_7,\ \color{red}{b_2b_3}b_4\color{red}{b_5b_6}b_7,\ \color{red}{b_2b_3}b_4b_5\color{red}{b_6b_7},\ b_2\color{red}{b_3b_4}\color{red}{b_5b_6}b_7,\cr
 b_2\color{red}{b_3b_4}b_5\color{red}{b_6b_7},\ b_2b_3\color{red}{b_4b_5}\color{red}{b_6b_7},\ \color{red}{b_2b_3}\color{red}{b_4b_5}\color{red}{b_6b_7}\cr}$$
and so
$$\eqalign{a_7&=b_2b_3b_4b_5b_6b_7+b_4b_5b_6b_7+b_2b_5b_6b_7+b_2b_3b_6b_7+b_2b_3b_4b_7\cr
&\qquad+b_2b_3b_4b_5+b_6b_7+b_4b_7+b_4b_5+b_2b_7+b_2b_5+b_2b_3+1\ .\cr}$$
It is not hard to prove by induction that this rule works.
