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.
 A: 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}$
A: I think the following works.
Let $N_k$ be the number of sequences of length $k$ that end for the first time in HTHT.
Now, the number of sequences of length $k$ that end in HTHT (possibly not for the first time) is $2^{k-4}$.  However, many of these had proper prefixes that ended in HTHT, and we have to subtract these out:

*

*$N_{k-2}$, the prefixes of length $k-2$ that end in HTHT.

*$N_{k-4}$, the prefixes of length $k-4$ that end in HTHT.

*$2N_{k-5}$, twice the prefixes of length $k-5$ that end in HTHT (because they are followed by an arbitrary result on flip number $k-4$).

*$4N_{k-6}$, four times the prefixes of length $k-6$ that end in HTHT (because they are followed by an arbitrary result on flips number $k-5$ and $k-4$).

*And so on.

We therefore have, for $k \geq 8$,
$$
N_k = 2^{k-4}-N_{k-2}-\sum_{j=4}^{k-4} 2^{j-4}N_{k-j}
$$
leading to OEIS A112575 (with an offset), with values
$$
1, 2, 3, 6, 12, 22, 41, 78, 147, 276, 520, 980, 1845, 3474, \ldots
$$
for $k \geq 4$.  The desired probabilities are then
$$
p_k = \frac{N_k}{2^k}
$$
