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}$$
