Find a system of recurrence relation for computing the number of n-digit binary sequences with exactly one pair of consecutive 0s. I tried solving this question from Alan Tucker's book, "Applied Combinatorics, 6th edition", Page no.294, Problem-35, but could not solve it.
I was thinking of finding the number of n-digit binary sequences which have at least two pairs of consecutive 0s and then subtracting the sum of both the number of ways to get no consecutive zeroes from $ 2^{n}$.
Am I correct with this approach?
 A: This is basically a more elaborate version of the comments by @user2661923. Spoiler: this is sequence A001629 in the OEIS.
These kind of questions can be approached quite mechanically by modeling them with a suitable state transition diagram. (It might not always be the easiest or most clever approach, but it always works.) Each state represents a specific category of sequences and counts the number of sequences of length $n$ that fall into that category.  A state transition matrix relates these states for length $n+1$ to those for length $n$.  In this case four states can be defined as follows

*

*The sequence ends with a zero and has no consecutive zeroes.

*The sequence ends with a one and has no consecutive zeroes.

*The sequence ends with a zero and contains precisely one pair of consecutive zeroes.

*The sequence ends with a one and contains precisely one pair of consecutive zeroes.

The state transition matrix is then $$ M = \begin{pmatrix} 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0\\
1 & 0 & 0 & 1\\
0 & 0 & 1 & 1 \end{pmatrix}.$$
For sequences of length $1$ the state vector $v_1$  equals $$ v_1 = \begin{pmatrix}1\\1\\0\\0\end{pmatrix}.$$ Then for length $n+1$ the state vector is given by $$v_{n+1} = M v_n = M^n v_1.$$ The number $a_n$ of sequence of length $n$ that we’re looking for is then the sum of the last two numbers in the state vector $v_n$ (so the sum of numbers in state $3$ and state $4$).
The sequence of state vectors begins as $$
\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix},
\begin{pmatrix} 1 \\ 2 \\ 1 \\ 0 \end{pmatrix},
\begin{pmatrix} 2 \\ 3 \\ 1 \\ 1 \end{pmatrix},
\begin{pmatrix} 3 \\ 5 \\ 3 \\ 2 \end{pmatrix},
\begin{pmatrix} 5 \\ 8 \\ 5 \\ 5 \end{pmatrix},
\begin{pmatrix} 8 \\ 13 \\ 10 \\ 10 \end{pmatrix}, \ldots$$
and the requested number $a_n$ of sequences is therefore $$0, 1, 2, 5, 10, 20, \ldots$$
There is also a simple linear recursion for this sequence. Note that the characteristic polynomial of $M$ equals $$\det(xI - M) = x^4 -2 x^3 - x^2 + 2 x + 1$$ and therefore the sequence satisfies the recursion $$a_{n+4}=2 a_{n+3}+ a_{n+2} - 2 a_{n+1} - a_n.$$
