Csdrhrt

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_iright)$$

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})$$

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_1left(frac{sqrt{5}+1}{4}right)^n+ sigma_2left(frac{1-sqrt{5}}{4}right)^n+sigma_3left(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$

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=ELambda E^{-1}$$
And this would imply:
$$M^n = E Lambda^n E^{-1}$$

So we get:
$$beta^n = ELambda^{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$.