2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Ross Millikan Nov 26 '18 at 20:35
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.