Given a fair coin, if we flip the coin $10$ times, what is the probability that the string of flips does not contain a $'HHH'$ or $'TTT'$ anywhere inside it?
That is, what is the probability that neither heads or tails shows up three times in a row? (As the title suggests)
Total number of outcomes: $2^{10}$
From seeing related posts and doing some googling, it seems a recurrence relation can be used to solve a problem of this sort, but I got stuck. I don't know if there is another way to solve this kind of problem. (Besides brute force of counting the outcomes we desire) The answer given to this question by N.F Taussig gave me a good start to setting up the problem, but their answer deals with the stipulation that only heads doesn't show up twice in a row.
Letting $a_n$ be the number of sequences of length $n$ that do not have $3$ consecutive heads or tails in them.
It is relatively straightforward to see that $a_1 = 2$, $a_2 = 4$, and $a_3 = 6$
If our sequence of length $n$ ends with $HH$, it must have a $T$ in the $n-2$ position.
If our sequence ends with $TT$, it must have a $H$ in the $n-2$ position.
I am unsure of how to go on from here.
I would also be interested in generalizing this process to $N$ flips of a fair coin where neither heads or tails shows up $k$ times in a row. ($k \ge 2$)
Thanks for any help given.
One approach is coupled recurrence relations. Let $b_n$ be the number of $n$ length sequences that end in one of the same letter, so they end in HT or TH (or are length $1$), and $c_n$ be the number of $n$ length sequences that end in two of the same, so HH or TT. We then have $$a_n=b_n+c_n\\b_n=b_{n-1}+c_{n-1}\\c_n=b_{n-1}\\b_1=2\\b_2=2\\c_1=0\\c_2=2$$ where the $b_n$ comes because we can we can put the other flip after any series and the $c_n$ comes because we can put another on if there is only one at the end so far. This gives $$b_n=b_{n-1}+b_{n-2}$$ so $b_n$ is just twice the Fibonacci numbers and $c_n$ is twice the Fibonacci numbers offset by $1$. $$b_n=2F_n\\c_n=2F_{n-1}\\a_n=2F_n+2F_{n-1}=2F_{n+1}$$