Suppose we are flipping a fair coin. Let $X$ be the waiting to the first occurrence of $TTHH$ (Tails, Tails, Heads, Heads). So if we got $HTTHH$, then $X=5$. Find the pmf of $X$.
Now I've tried conditioning on the first flip ($X_1$) but I get nowhere:
$$\begin{align} P(X=n) &= \frac{1}{2}P(X=n|X_1=T)+\frac{1}{2}P(X=n|X_1=H) \\ &=\frac{1}{2}P(X=n|X_1=T)+\frac{1}{2}P(X=n-1) \\ \end{align}$$
I'm not sure where to go from here or even if this is the right approach. I've even tried to mess around with Markov Chains but can't seem to get anywhere.
One can easily see that $P(X \le 3)=0$ and $P(X=4) = \frac{1}{2^4}=\frac{1}{16}$. To get $P(X=5)$ we need to get TTHH in the last 4 throws and to not get TTHH on the first roll, so $P(X=5)=\frac{1}{16}(1-P(X=1))=\frac{1}{16}$. Similarly $P(X=6)=\frac{1}{16}(1-P(X \le 2))=\frac{1}{16}$ and $P(X=7)=\frac{1}{16}(1-P(X \le 3))=\frac{1}{16}$. After 8 throws we have $P(X=8)=\frac{1}{16}(1-P(X \le 4))=\frac{1}{16}(1-\frac{1}{16})=\frac{15}{256}$.
In general we have: $$P(X=x)=\frac{1}{16}(1-P(X \le (x-1)))=\frac{1}{16}-\frac{1}{16}\sum_{k=0}^{x-1}P(X=k)$$ I don't know how to find a closed form for this answer.