Here is another way to obtain a set of recursive equations for determining $P_n$, the probability that there is a string of $k$consecutive heads in a sequence of $n$flips of a fair coin that comes up heads with probability $p$:

(a) Argue that for $k<n$, there will be a string of $k$consecutive heads if either

1. there is a string of $k$consecutive heads within the first $n-1$flips, or

2. there is no string of $k$consecutive heads within the first $n-k-1$flips, flip $n-k$is a tail, and flips $n-k+1,\dots ,n$are all heads.

(b) Using the preceding, relate $P_{n}to{P}_{n-1}$. Starting with $P_k=p^k$, the recursion can be used to obtain $P_{k+1}$, then$P_{k+2}$, and so on, up to $P_n$.

We found that there is another way to obtain a set of recursive equations for determining $P_n$, the probability that there is a string of $k$consecutive heads in a sequence of $n$flips of a fair coin that comes up heads with probability $p$.

Let's condition on what happens with the last$k$ flips. We have two options

1

There has been obtained $k$consecutive Heads within first $n-1$flips. That means that we are not interested what happens in the last trial (the probability l), so the probability for this case is $P_{n-1}$.

2

Suppose that we have obtained $k$consecutive Heads in the last $k$flips. That means that in $n-k-1$st flip we had to have tail and that in the first $n-k-1$flips we have not obtained $k$consecutive heads.

We found that there is another way to obtain a set of recursive equations for determining $P_n$, the probability that there is a string of $k$consecutive heads in a sequence of $n$flips of a fair coin that comes up heads with probability $p$.

Considering the discussion in (a), the required recursion is

$P_n=P_{n-1}+(1-p)·\left(1-P_{n-k-1}\right)·p^k$

That recursive relation can be solved using the method given in the exercise, but it is not part of this task.