Constructing a recurrence relation regarding binary sequences

Question

For each positive integer $n$, let $a_n$ be the number of binary sequences of length $n$ which do not contain the subsequence $011$. Construct a recurrence relation for $a_n$.

My attempt:
Initial conditions: $a_1 = 2, a_1 = 4, a_3 = 7$
Recurrence relation: For $n \ge 4$, $a_n = a_1 * a_{n-1} - a_{n-3}$

My reasoning is that $a_1$ and $a_{n-1}$ themselves do not contain $011$, so the only way $011$ could occur is if $a_1$ starts with $0$ and $a_{n-1}$ starts with $11$. So I subtract $a_{n-3}$ to avoid counting those subsequences that start with $011$. Is this valid?

Thanks in advance.

Answer 1

Your reasoning is correct, but the language in which you couch it is not. You write:

My reasoning is that $a_1$ and $a_{n-1}$ themselves do not contain $011$, so the only way $011$ could occur is if $a_1$ starts with $0$ and $a_{n-1}$ starts with $11$.

You’re speaking of $a_1$ and $a_{n-1}$ as if they were binary sequences, when in fact they are non-negative integers: $a_k$ is the number of binary sequences of length $k$ that do not contain $011$. Here’s one way to express the same idea correctly.

Say that a binary sequence is good if it does not contain the subsequence $011$. Let $\sigma$ be a good sequence of length $n>1$; then $\sigma=b\tau$, where $b\in\{0,1\}$ and $\tau$ is a good sequence of length $n-1$. There are $2$ possible values for $b$ and $a_{n-1}$ for $\tau$, so there are $2a_{n-1}$ possible sequence of the form $b\tau$ with $\tau$ a good sequence of length $n-1$. All of those sequences are good except the ones that begin $011$, so we need to determine how many of these there are and subtract that number from $2a_{n-1}$.

These are the ones for which $b=0$ and $\tau=11\rho$ for some binary sequence of length $n-3$. We know that $\tau$ is good, so $\rho$ must also be good. Conversely, if $\rho$ is any good sequence of length $n-3$, $\tau=11\rho$ is a good sequence of length $n-1$ to which we cannot prefix a $0$ to get a good sequence of length $n$. Thus, there are $a_{n-3}$ good sequence of length $n-1$ that begin $11$ and hence $a_{n-3}$ sequences of the form $b\tau$ that must be subtracted from $2a_{n-1}$ to yield $a_n$. That is, the desired recurrence is $a_n=2a_{n-1}-a_{n-3}$.

Answer 2

Try splitting into two:

$S_n = $ number of sequences that start with $1$ and $T_n = $ the number those start with $0$.

We have $a_n = S_n + T_n$.

Now to get $a_{n+1}$ from lower values:

If we start with $1$, we can have $a_n$ choices for the rest. This also means $T_{n+1} = a_n$.

If we start with $01$, then we have $T_{n-1} = a_{n-2}$ choices for the rest.

If we start with $00$, then we have $a_{n-1}$ choices for the rest.

Thus

$$a_{n+1} = a_n + a_{n-2} + a_{n-1}$$