# Recurrence Relation Trouble Understanding Where I Went Wrong

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?

• Good for you for checking your recurrence with the data you have and showing your work carefully. A couple typos: I would say $b_n$ is the number of binary sequences starting with $0$... When you are counting the strings that begin with $00$ the next digit can only be $1$ – Ross Millikan Nov 26 '18 at 20:35

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