The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Consider the preliminary question of getting a sequence of $$N$$ heads out of $$k$$ throws, with probability $$p(N,k)$$. This is given by the recurrence formula $$p(N,k) = \begin{cases} 0 &\text{if } k (with the convention that sums are equal to zero if the upper bound is strictly less than the lower bound). Indeed, my reasoning is that the first consecutive N heads have to be preceded by a tail and no other consecutive N heads before. If there are $$m steps before, this is not possible so any sequence of $$m$$ throws can occur. When $$m\ge N$$, it is possible and has to be excluded.
Next, the probability of getting the first consecutive N heads in $$m\ge N$$ throws is $$q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N
Now, the probability to get $$M$$ heads first and $$N$$ heads in exactly $$m\ge N$$ throws is $$r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N