<s>[INST] Probability of HTHT in n coin flips What is the probability of finding the sequence HTHT in $n$ flips of a coin? By brute force I get

*

*$n=4: \frac{1}{2^4}$

*$n=5: \frac{2(2)}{2^5}$

*$n=6: \frac{2^2(3)-1}{2^6}$

*$n=7: \frac{2^3(4)-2}{2^7}$

*$n=8: \frac{2^4(5)-6}{2^8}$
I hoped to extract a pattern but counting gets messy.
EDIT: My original counts for $n=7$ and $n=8$ are, as noted in the comments, incorrect. Recounting I get
\begin{align}
\frac{2^3(4)-4}{2^7}\ \text{for}\ n=7\ \text{and}\ \frac{2^4(5)-12}{2^8}\ \text{for}\ n=8
\end{align}
which agrees with the comment below.
 [/INST] Let $A_n$ be the number of sequences that don't include the pattern $HTHT$. Then
$$A_n = \pmatrix{1 & 1 & 1 &1} T^n  {\pmatrix{1 & 0 & 0 &0}}^{t} \tag1$$
where
$$T= \pmatrix{ 
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 1 & 0 &0 \\
0 & 0 & 1 &0 
} \tag2$$
Eq $(1)$ is obtained by counting recursively the "allowed" sequences that have $(0,1,2,3)$  trailing matching characters.
Some values for $A_n$, from $n=0$ to $n=10$: $(1, 2,4,8,15,28,53,100,188,354,667)$
This is OEIS sequence A118870.
Then the desired probability is
$$ p_n = 1 - \frac{A_n}{2^{n}}$$
I don't think there is a simple formula to express $(1)$ for arbitrary $n$
I'd expect that $p_n \le 1 - (15/16)^{n-3}$
</s>