# Probability of no pair of consecutive heads in $n$ flips of a coin

I am trying to solve the following problem. A biased coin shows heads with probability $$p=1-q$$ when it is flipped. Let $$u_{n}$$ be the probability that in $$n$$ flips, no pair of heads occur successively. Show that for $$n \geq q$$,

$$u_{n+2} = qu_{n+1} + pqu_{n}.$$

I know I need to use the partition theorem $$P(X) = \sum P(X|B_{i})P(B_{i})$$ where the set of events $$B_{i}$$ partition the sample space (the question event gives the hint "use partition theorem with $$B_{i}$$ the event that first $$i-1$$ flips yield heads and the $$i$$th yields tails"), but I still have no idea as to how to proceed and to how to choose the partition. I intuitively see why the answer is what it is, but I can't rigorously formulate the approach to the solution in my head.

Decompose $$u_n=a_n+b_n$$, where the latter two sequences are defined like $$u_n$$ except that they only consider those sequences ending in a head or a tail respectively. Then $$\begin{bmatrix}a_{n+1}\\b_{n+1}\end{bmatrix}=\begin{bmatrix}0&p\\q&q\end{bmatrix}\begin{bmatrix}a_n\\b_n\end{bmatrix}$$ From this we derive $$\begin{bmatrix}a_{n+2}\\b_{n+2}\end{bmatrix}=\begin{bmatrix}pq&pq\\q^2&pq+q^2\end{bmatrix}\begin{bmatrix}a_n\\b_n\end{bmatrix}$$ and hence $$u_{n+2}=a_{n+2}+b_{n+2}=pq(a_n+b_n)+q^2a_n+(pq+q^2)b_n$$ $$=pqu_n+q(qa_n+(p+q)b_n)=pqu_n+qu_{n+1}$$

Let's follow the (clever) hint. Let $$U_{n}$$ be the event of interest, so that $$P(U_n)=u_n$$.

Let $$B_i$$ be the event that, in $$i$$ flips, the first $$i-1$$ flips yield head and the $$i$$th yields tails. Let $$A_i$$ be the event that, in $$i$$ flips, all are head. Clearly, the events $$\{A_j, B_1, B_2 , B_3, \cdots B_j \}$$ are disjoint and exhaustive for any given $$j\ge 1$$.

Then, for any $$n\ge 0$$ $$u_{n+2}=P(U_{n+2})=P(U_{n+2}|A_{n+2})P(A_{n+2}) + \sum_{i=1}^{n+2} P(U_{n+2}|B_i)P(B_i)$$

Now, $$P(U_{n+2}|B_i)=0$$ if $$i>2$$ (we had at least two consecutive heads); same goes for $$P(U_{n+2}|A_{n+2})=0$$.

Further, $$P(U_{n+2}|B_1)=P(U_{n+1})$$ and $$P(U_{n+2}|B_2)=P(U_{n})$$.

Hence $$u_{n+2}=u_{n+1} q + u_{n} \, p \, q$$

Am I missing something? The recurrence can be explained super-easily if you just condition on the last flip, right?

• If the last flip is T, the $$(n+2)$$-sequence is good iff the initial $$(n+1)$$-subsequence is good.

• If the last flip is H, the $$(n+2)$$-sequence is good iff the second-to-last flip is T and the initial $$n$$-subsequence is good.