Number of sequences of length $m$ such that $1$ is never followed immediately by $0$

We may consider a Markov chain with three states $\{0,1,2\}$, corresponding to the last parsed character. The adjacency matrix of such a Markov chain is $$ P=\begin{pmatrix}1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{pmatrix} $$ (so just the transition $0\mapsto 1$ is not allowed) and the number $S_m$ of strings of $m\geq 1$ characters with the given property is the sum of the elements of $P^{m-1}$. You may now compute $S_m$ from a spectral decomposition of $P$. The usual combinatorial way is to consider that any valid string with length $m$ may only start with a prefix among $$ 1,\quad 2,\quad 02,\quad 002,\quad 0002,\quad \ldots,\quad 000\ldots000.$$ It follows that, by setting $S_0=1$, $$ S_m = 2 S_{m-1} + S_{m-2} + S_{m-3} + \ldots + S_{0} $$ $$ S_{m+1} = 2 S_{m} + S_{m-1} + S_{m-2} + \ldots + S_{0} $$ $$ S_{m+1}-S_{m} = 2S_m-2S_{m-1}+S_{m-1} $$ and $$ S_{m+1} = 3S_{m}-S_{m-1},\quad S_0=1, S_1=3 $$ so $$\boxed{ S_m = \frac{1}{\sqrt{5}}\left[\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}\right]=\color{red}{F_{2n+2}} }$$ the number of our strings is given by a Fibonacci number. A combinatorial bijection showing the same can be the following one: if we map $0\mapsto 01$, $1\mapsto 10$, $2\mapsto 00$, the valid strings having length $n$ are mapped into the binary strings of length $2n$ with the property that two "$1$s" are never next to each other. For instance: $$ 021002 \mapsto 010010010100 $$ and the latter problem is a famous problem.

HINT: Call such sequence good, and let $a_n$ be the number of good sequences of length $n$. If $\sigma$ is a good sequence of length $n$, we can form $3a_n$ sequences of length $n+1$ by appending a $0,1$, or $2$ to the end of $\sigma$. Every good sequence of length $n+1$ can be obtained in this way, but unfortunately so can some bad ones. The bad ones are those that end in $10$. These are clearly obtained by appending $01$ to a good sequence of length $n-1$, and there are $a_{n-1}$ of those, so our count of $3a_n$ includes exactly $a_{n-1}$ bad sequences, and we find that $a_{n+1}=3a_n-a_{n-1}$, or

$$a_n=3a_{n-1}-a_{n-2}\tag{1}$$

with initial values $a_0=1$ (because the empty sequence is good) and $a_1=3$.

Now use your favorite method to solve the recurrence $(1)$ to get a closed form for $a_n$.

A Shortcut: If you calculate the first few $a_n$, you get the following table:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6\\ a_n:&1&3&8&21&55&144&377 \end{array}$$

If you recognize the bottom row as a subsequence of some familiar sequence, you may be able to prove that it really is that subsequence and use that to get a closed form more easily.

Added: Since Jack D’Aurizio has now mentioned the Fibonacci numbers explicitly, I’ll elaborate on the shortcut bit. It’s quite well known (and easy to show) that the number of ways to tile a $1\times n$ strip using $1\times 1$ and $1\times 2$ tiles (monominoes and dominoes) is $F_{n+1}$. Thus, there are $F_{2n+2}$ ways to tile a strip of length $2n+1$. Number the cells of the strip $1$ through $2n+1$ from left to right, and suppose that we have a tiling of the strip by monominoes and dominoes. Label each even-numbered cell $L$ if it’s covered by the left half of a domino, $R$ if it’s covered by the right half of a domino, and $S$ if it’s covered by a monomino. There are $n$ even-numbered cells, so this labelling produces a string of length $n$ over the alphabet $\{L,R,S\}$. The only restriction on these strings is that they cannot contain the substring $LR$ (why?). Thus, there are $F_{2n+2}$ strings of length $n$ over the alphabet $\{L,R,S\}$ in which $L$ is never followed by $R$. Replace $L,R$, and $S$ by $1,0$, and $2$, respectively, to map these strings to the ones in the problem.

For variety, let $A_n$ be the number of such sequences of length $n$ that end in a $1$.

Let $B_n$ be the number of such sequences of length $n$ that do not end in a $1$.

Then,

• $A_0 = 0$
• $B_0 = 1$
• $A_{n+1} = A_n + B_n$
• $B_{n+1} = A_n + 2 B_n$

You can use your favorite method to solve this recurrence relation.

(phrases for further searching: "linear recurrence", "difference equation")