# Probability of at least one k-length run of heads in n coin flips

Question says it all - the flips are uniform, independent events that can be Heads or Tails. My strategy has been to find the probability of having no k-length runs of heads in n flips, and take 1 minus that. I think the solution has to do with recursion/induction, but I’m not sure exactly how it works...

• Well, a (sufficiently long) good string must end in one of $T, TH, TH^2, \cdots, TH^{k-1}$ so you can get a recursion. (Note: here a "good" string is one without a string of at least $k$ consecutive Heads). – lulu May 16 '18 at 20:12

The probability of any particular outcome of heads and tails in n flips is $0.5^n$. The number of outcomes is $\frac{1}{0.5^n}$. Obviously $0.5^n\cdot \frac{1}{0.5^n}=1$ so the probability of not getting a single k length run of heads is:
$$1 - (n-(k-1))0.5^n$$ Where $(n-(k-1))$ is the number of ways to get a k length run of heads in n flips.
$$1 - (n-(k-1))0.5^n - ((n-(k+1))-(k-1))0.5^n - ((n-(k+2))-(k-1))0.5^n..........(1)0.5^n$$