probability - Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills may improve if I see one or two examples with some explanation.

For example, let's consider the problem of the probability of getting at least $k$ consecutive heads when tossing a coin $n$ times. The following recursive equation for this problem has been posted here in terms of probabilities:
$$
P(N,k)=P(N-1,k)+\Big(1-P(N-k-1,k)\Big)\left(\frac{1}{2}\right)^{k+1}
$$

This equation seems to be correct when plugging a few numbers in. My questions are:

• What is the mind process for arriving at such equations? Are there any systematic approaches, or at least some helpful tips?


• What if, in general, the probability of obtaining a heads is $p$? Can one still have recursive equation in this case?

Answer

The logic for that recurrence is that to have a run of $k$ heads out of $N$ flips, you can either have a run out of the first $N-1$ flips and the last one can be anything (the first term on the right) or you can have no run in the first $N-k-1$ flips (the $\Big(1-P(N-k-1,k)\Big)$ term), then a tail (the first factor $\frac 12$), then $k$ heads (the factor $\left(\frac 12 \right)^k$). In general, one way is to carefully enumerate the possibilities.

If the probability of a head were $p$ instead of $\frac 12$ the final $\left(\frac 12 \right)^{k+1}$ would become $(1-p)p^k$, following the logic in the previous paragraph.