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.
 A: 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}$$
A: 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$$
A: 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.
