Probability of a run of 3 heads when I flip a coin $n$ times I'm wondering if there is a nice solution for this problem. As stated, I flip a coin $n$ times, and want the probability of a run of 3 (or more) heads appearing within it. For example, if I toss a coin 9 times, an example that would include a run of 3 heads is TTHHHTHTH, as is THTHHHHHT, but TTHHTHTTH is not.

Generalisations to runs of $m$ (or more) heads also welcome!
The time $T_{m+1}$ needed to get a run of $m+1$ heads is $$T_{m+1}=T_m+1$$ with probability $p_H=\frac12$ and $$T_{m+1}=T_m+1+T'_{m+1}$$ with probability $p_T=1-p_H=\frac12$, where $T'_{m+1}$ is distributed like $T_{m+1}$ and independent of $T_m$. 

Thus, the generating functions $g_m(s)=E(s^{T_m})$ are such that


  $$g_{m+1}(s)=\frac12s(g_m(s)+g_m(s)g_{m+1}(s))\tag{$\ast$}$$ 


From there, the solution is standard. First, $(\ast)$ can be rewritten as $$g_{m+1}(s)=\frac{sg_m(s)}{2-sg_m(s)}$$ hence $$\frac1{g_{m+1}(s)}-\frac{s}{2-s}=\frac2s\left(\frac1{g_m(s)}-\frac{s}{2-s}\right)$$ that is, using $g_0(s)=1$,$$\frac1{g_m(s)}=\left(\frac2s\right)^m\left(1-\frac{s}{2-s}\right)+\frac{s}{2-s}$$ from which every $g_m(s)$ follows as


  $$g_m(s)=\frac{s^m(2-s)}{2^{m+1}(1-s)+s^{m+1}}$$


For example, for $m=1$, $$g_1(s)=\frac{s^2}{2-s}$$ that is, $T_1$ is a shifted geometric random variable. More generally, recall that each function $g_m$ fully encodes the distribution of $T_m$ since, by definition, $$g_m(s)=\sum_{k=0}^\infty P(T_m=k)s^k$$ thus, expanding $g_m(s)$ as a power series yields every $P(T_m=k)$. If one is interested to observe a run of length $m$ during the $k$ first draws, one would simply compute $$P(T_m\leqslant k)$$
Let $H_m$ be the event that the $m$th toss is heads. Then 3 heads is $$A_m := H_m \cap H_{m+1} \cap H_{m+2}$$

where $m = 1$ to $n-2$. Thus, by inclusion-exclusion, a probability of a run of 3 heads is

$$P(\bigcup_{k=1}^{n-2} \bigcap_{i=0}^2 H_{k+i}) = P(\bigcup_{k=1}^{n-2} A_k)$$

$$ = \sum_{i=1}^{n-2} P(A_i) - \sum_{1 \le i &lt; j \le n-2} P(A_i \cap A_j) + \sum_{1 \le i &lt; j &lt; k \le n-2} P(A_i \cap A_j \cap A_k)$$

Now, $P(A_i \cap A_j \cap A_k) = 0$ unless $i+2=j+1=k$ in which case we have $P(A_i \cap A_j \cap A_k) = P(H_k)$

Similarly, $P(A_i \cap A_j) = 0$ unless $i+1=j$ or $i+2=j$ in which cases we respectively have $P(A_i \cap A_j) = P(H_j \cap H_{j+1})$ and $P(A_i \cap A_j) = P(H_j)$