Recurrence Relation Trouble Understanding Where I Went Wrong

Question

I'm studying for my exam in my combinatorics class, and we received a review sheet. I am stuck on this question about recurrence relations:

Let $a_n$ be the number of binary sequences of length $n$ which do not contain the sequence $001$.

(a) Find $a_1$, $a_2$, $a_3$, and $a_4$.

(b) Find a recurrence relation for the sequence $a_n$.

So, I did part (a) as follows:

$a_1:$ $0$ or $1$ $\implies$ $a_1=2$

$a_2:$ $00$, $01$, $10$, or $11$ $\implies$ $a_2=4$

$a_3:$ $2^3$ ways to write a binary sequence of 3 digits, $001$ is the only bad option $\implies$ $a_3=2^3-1=7$

$a_4:$ $001$* and *$001$ are bad options, so there are $2^4$ ways to write a binary sequence consisting of four digits, and for each of the bad options there are 2 ways to write them $\implies$ $a_4=2^4-2(2)=12$.

So, I have $a_1=2$, $a_2=4$, $a_3=7$, and $a_4=12$.

Then, I completed part (b) as follows:

$a_n=b_n+c_n$ where $b_n$ is the binary sequences starting with $0$s that do not contain the sequence $001$ and $c_n$ is the binary sequences starting with $1$s that do not contain the sequence $001$.

So $c_n$ has two possible beginnings to the sequence:

$10$ _ _ _ _ _ _... $\implies$ which is exactly $b_{n-1}$

$11$ _ _ _ _ _ _... $\implies$ which is exactly $c_{n-1}$

Thus, $c_n=b_{n-1}+c_{n-1}=a_{n-1}$.

$b_n$ can be either of the two following sequences:

$00$ _ _ _ _ _ _... $\implies$ the next digit can only be a $0$, so this sequence would be written as $000$ _ _ _ _ _... which is exactly $b_{n-2}$

$01$ _ _ _ _ _ _... $\implies$ this sequence is just $c_{n-1}$.

Thus, $b_n=c_{n-1}+b_{n-2}$.

So, $a_n=b_n+c_n$, $b_n=c_{n-1}+b_{n-2}$, and $c_n=a_{n-1}$.

Then, these equations can be written in terms of only $a_n$ and $b_n$ as follows:

$a_n=b_n+a_{n-1}$ and $b_n=a_{n-2}+b_{n-2}$

$b_n=a_n-a_{n-1}$ $\implies$ $b_n=a_{n-2}+a_{n-2}-a_{n-3}$.

Thus, $a_n=a_{n-1}+2a_{n-2}-a_{n-3}$.

However, if this were the case then $a_4=a_3+2a_2-a_1=7+2(4)-2=13$ and I got that $a_4$ is 12 from going through the cases. Did I count wrong when I was originally determining what $a_4$ is or did I find the recurrence in a wrong way?

Answer 1

The error occurs when you are counting strings of the type $00...$ within $b_n$. Clearly, the next digit cannot be $1$, so it has to be $0$. Now you get $000...$, and once again the next digit cannot be $1$. Carry this on until you reach the end of the string, so that the only string you get from this case is $0000..0$ with no $1$s at all. $\implies b_n=c_{n-1}+1\implies a_n=a_{n-1}+a_{n-2}+1, n>2.$

Answer 2

Your count of $a_4=12$ is correct. The problem with the recurrence comes when you say that the part of $b_n$ that starts with $00$ is the part that starts $000$ (this is true) but then say this is $b_{n-2}$. $b_{n-2}$ includes strings that begin $01$ so you cannot put $00$ in front of them all. With your recurrence $b_4=6$, but there are only five strings: $0000,0100,0101,0110,0111$, but you include $0001$ as well.