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})$$
 A: The homogeneous part of $b_{n}−b_{n−1}=\frac{1}{8}(1−b_{n−3})$ is given by:
$$8b_{n}-8b_{n-1}+b_{n-3}=0$$
So the characteristic equation is given by:
$$8l^3-8l^2+1=0$$
The roots are given by $l=\frac{1-\sqrt{5}}{4}, \frac{1+\sqrt{5}}{4},\frac{1}{2}$
And the answer can be taken as a constant: $b_n=c$. Substituting in 
$$8b_n+8b_{n-1}-b_{n-3}=1$$
We have $c=\frac{1}{15}$
Therefore the general solution can be written as:
$$b_n=\sigma_1\left(\frac{\sqrt{5}+1}{4}\right)^n+ \sigma_2\left(\frac{1-\sqrt{5}}{4}\right)^n+\sigma_3\left(\frac{1}{2}\right)^n+\frac{\sigma_4}{15}.$$
And for the two consecutive heads problem, we can use the first few values in the sequence $b_n$ in particular, $b_0=0$, $b_1=0$, $b_2=0.25$ and $b_3=0.375$ to get $\sigma_1 = -1.1708$, $\sigma_2=1.708$, $\sigma_3=0$, $\sigma_4=15$
A: 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$.
