Solving a difference equation for coin toss sequence probabilities I want to solve the following difference equation:
$$b_n-b_{n-1} = \frac{1}{8}(1-b_{n-3})$$
I tried to solve it similar to the solution of Fibonacci sequence here, but when I try to assume the solution will be of the form $l^n$, I end up with the following polynomial:
$$l^{n-3}(l^3-l^2+\frac{1}{8}) = \frac{1}{8}$$
Unlike in the Fibonacci sequence, we don't get a polynomial equation that can be easily solved and independent of $n$.
Any other strategy to solve this?

The reason I care about this difference equation is that it describes the probability I will get two consecutive heads on the $n$th toss of a fair coin.
Let $a_n$ be the probability that I'll reach two consecutive heads on the $n$th toss.
We know that at the time when I reach my goal on the $n$th toss, the last two tosses I saw would have both been heads. 
Also, the third-from-final toss would have had to be a tails (otherwise, I would have won one toss earlier). The probability of this sequence
of THH is $\frac{1}{2}\times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$.
Before these three tosses, my probability of winning would have been by definition, $a_{n-3}$. But if I am to win in the $n$th toss,
I need to exclude that event. And similarly $a_{n-4}$ and so on. This means:
$$a_n=\frac{1}{8}\left(1-\sum_{i=1}^{n-3} a_i\right)$$
Now let's define:
$$b_n = \sum_{i=1}^{n} a_i$$
which represents the probability you would have won by the $n$th toss.
Plugging this equation into the previous one we get:
$$b_n-b_{n-1} = \frac{1}{8}(1-b_{n-3})$$

I have another approach to this I just worked out. Here, we try to use express the recurrence as a system of linear equations. Then, we leverage the eigen values of the matrix associated with the matrix of this linear system. 
So far, we have only one equation. This is:
$$b_n -b_{n-1} + \frac{1}{8}b_{n-3} = \frac{1}{8}$$
To form a linear system, we need two more equations. Let's take some dummy equations.
$$b_{n-1}=b_{n-1}$$
$$b_{n-2}=b_{n-2}$$
Now, we can express this system in matrix form.
$$\left( \begin{array}{c}
  b_n \\
  b_{n-1}\\
  b_{n-2}\\
  \end{array} \right) = \left( \begin{array}{ccc}
  1 & 0 & -\frac{1}{8} & \\
  1 & 0 & 0\\
  0 & 1 & 0\\
  \end{array} \right) \left( \begin{array}{c}
  b_{n-1} \\
  b_{n-2}\\
  b_{n-3}\\
  \end{array} \right) + \left( \begin{array}{c}
  \frac{1}{8} \\
  0\\
  0\\
  \end{array} \right)$$
Now let:
$\beta_n = \left(\begin{array}{c}
  b_n \\
  b_{n-1}\\
  b_{n-2}\\
  \end{array} \right)$, $\gamma = \left(\begin{array}{c}
  \frac{1}{8} \\
  0\\
  0\\
  \end{array} \right)$ and $M = \left( \begin{array}{ccc}
  1 & 0 & -\frac{1}{8} & \\
  1 & 0 & 0\\
  0 & 1 & 0\\
  \end{array} \right)$.
We then get:
$$\beta_n = M \beta_{n-1} + \gamma$$
$$=M(M \beta_{n-2}+\gamma) + \gamma$$
$$=M^2 \beta_{n-2} + (I+M)\gamma$$
Extending this all the way we get:
$$\beta_n = M^{n-2}\beta_{2} + (I+M+M^2+ \dots + M^{n-3})\gamma$$
Now, assuming $M$ is diagonalizable (which it is) we can say:
$$M=E\Lambda E^{-1}$$
And this would imply:
$$M^n = E \Lambda^n E^{-1}$$
So we get:
$$\beta^n = E\Lambda^{n-2}E^{-1}\beta_2 + E(I+\Lambda+\Lambda^2+\dots+\Lambda^{n-3})E^{-1}\gamma$$
Now, if $\lambda_1$, $\lambda_2$ and $\lambda_3$ happen to be the eigen values of $M$ then,
$$\Lambda = \left( \begin{array}{ccc}
  \lambda_1 & 0 & 0 & \\
  0 & \lambda_2 & 0\\
  0 & 0 & \lambda_3\\
  \end{array} \right)$$
and,
$$(I+\Lambda+\Lambda^2 + \dots + \Lambda^{n-3}) = \left( \begin{array}{ccc}
  \frac{1-\lambda_1^{n-2}}{1-\lambda_1} & 0 & 0 & \\
  0 & \frac{1-\lambda_2^{n-2}}{1-\lambda_2} & 0\\
  0 & 0 & \frac{1-\lambda_3^{n-2}}{1-\lambda_3}\\
  \end{array} \right)$$
Using these, it is easy to see that:
$$\beta_n = c_0 + c_1 \lambda_1^{n-2} + c_2 \lambda_2^{n-2} + c_3 \lambda_3^{n-2}$$
And the eigen values happen to be: $\lambda_1, \lambda_2, \lambda_3 = \frac{\phi}{2}$, $\frac{1-\phi}{2}$, $0.5$.
