How would one write a recursion for the number of ways to get 4 or more heads in a row in 10 tosses of a coin? Would it suffice to use the recursion H(n)=H(n-1)+H(n-2)+H(n-3)+H(n-4) for the number of ways this does not occur?
Is there a better way to count this non-recursively? For example, is it possible to count directly, conditioning on the number of heads as follows: $1+2(2^1)+3(2^2)+4(2^3)+5(2^4)+6(2^5)+7(2^6)$, also subtracting off the relevant additional cases. In general, $(n-(k-1))!(\sum_{i=k}^{n-(k-1)} (2^{n-k}-2^{n-k+1})$ where n is the number of trials, and k is the number of a binary outcome in a row we want (is this right)?
If $H(n)$ counts the number of ways you don't end up with 4 or more heads out of $n$ flips, you don't need recursion. The probability of not tossing four or more heads is that number divided by total possible flips, $\frac{H(n)}{2^n}$, so the probability of tossing four or more heads is the complement $1 - \frac{H(n)}{2^n}$.