N coin flips with at least three times heads or tails in a row (recursive probability) Suppose I'll be flipping a fair coin $n$ times. Now I want to calculate the probability that I'll get at least three times heads or tails in a row. 
The goal of this exercise is to get a recurrence formula of this kind.
$p_n = a \cdot p_{n-1} + b \cdot p_{n-2} + c \qquad (n\geq 3)$
And we have to use the law of total probability to get to the recursion.
I got to a formula with a different way. Suppose $q_n$ is the number of constellations that do not have three heads or tails. Then with $q_1=2$ and $q_2=4$ (because then 3xH or 3xT is not possible) we have $q_n = q_{n-1}+q_{n-2}$. Then
$p_n = \frac{2^n - q_n}{2^n}$
This is obviously not the way I have to tackle this problem. How do I get a recursion with the law of total probability?
 A: Let $p_n$ be the probability of getting a sequence of three heads or tails in $n$ trials.


*

*For $n$ trials, whatever the first flip is, the second will either be a repeat of it or it will not. $\frac 12$ chance of either:


*

*If it's not a repeat, we recurse for $n-1$ trials. This is: $p_{n-1}$

*If it is a repeat, then the third coin will either be a repeat or it will not, at $\frac 12$ chance of either:


*

*If it is not a repeat, we recurse for $n-2$ trials. That is: $p_{n-2}$

*If it is a repeat we have encountered a sequence of three heads or tails.
$\therefore p_n = \underline{\text{ ? }}\; p_{n-1} + \underline{\text{ ? }}\; p_{n-2} + \underline{\text{ ? }}$
Base case: $p_1=0, p_2=0, p_3 = \frac 14$ and so on.
Fill in the blanks.

Let $T_n$ be the event that a string of $n$ coin flips contains a substring of either three heads or of three tails.
Let $D_x$ be the event that the $x$ indexed flip in a sequence repeats the result of the $x-1$ indexed flip.  Each event is conditionally independent because whatever the previous flip result, the probability of repeating it remains identical (for unbiased coins).
By the Law of Total Probability:
$\begin{align} \operatorname{P}(T_n) &= \operatorname{P}(T_n \cap D_2) + \operatorname{P}(T_n\cap \neg D_2) \\ & = \operatorname{P}(T_n\mid D_2)\operatorname{P}(D_2) + \operatorname{P}(T_n\mid \neg D_2)\operatorname{P}(\neg D_2) \\ & = \operatorname{P}(T_n\mid D_2, D_3)\operatorname{P}(D_3)P(D_2) + \operatorname{P}(T_n\mid D_2, \neg D_3)\operatorname{P}(\neg D_3)\operatorname{P}(D_2) + \operatorname{P}(T_n\mid \neg D_2)\operatorname{P}(\neg D_2)  \end{align}$
Now $\operatorname{P}(T_n\mid \neg D_2) = \operatorname{P}(T_{n-1})$ since, when given the second flip is not a duplicate then the first flip cannot be part of the sought substring, so it is only possible to find it among the remaining string of $n-1$ flips.
Similarly $\operatorname{P}(T_n \mid D_2,\neg D_3) = \operatorname{P}(T_{n-2})$.
However, since if the second and third flips are both duplicates of the first flip, then we have found the sought substring, so: $\operatorname{P}(T_n\mid D_2, D_3) = 1$ 
So: $\begin{align} \operatorname{P}(T_n) & = 1\times \operatorname{P}(D_3)\operatorname{P}(D_2) + \operatorname{P}(T_{n-2})\operatorname{P}(\neg D_3)\operatorname{P}(D_2) + \operatorname{P}(T_{n-1})\operatorname{P}(\neg D_2) \end{align}$
