2
$\begingroup$

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving the last two.

We are asked to find a recursive formula (for example $f(n) = 2f(n-1)+f(n-2)+3$) for the following binary sequences (only digits allowed are $0$ and $1$):

1) binary sequence without the sub sequence $11$

2) without the sub sequence $01$

3) without the sub sequence $000$

4) without the sub sequence $011$

5) without the sub sequence $010$

My answers

1) let $f(n)$ be the number of sequences without $11$. if the sequence starts with $0$ then we have $f(n-1)$ for the other digits, if it starts with 1 then it has to be followed by a $0$ and then we have $f(n-2)$ for the other digits, so overall we get $f(n) = f(n-1)+f(n-2)$

2) let $f(n)$ be the number of sequences without $01$. if the sequence starts with $1$ then we have $f(n-1)$ options for the other digits, if it starts with $0$ then the entire sequence must be $0000...0$ that is the only option., so $f(n)=f(n-1)+1$

3) let $f(n)$ be the number of sequences without $000$. if the first digit is $1$ then we have $f(n-1)$ options for the rest. if it's $0$ then we need to look at the second digit, if it's $1$ then we have $f(n-2)$ for the other digits. if it's zero then we need to look at the third digit. The third digit must be $1$ and after that $f(n-3)$ options for the rest. overall $f(n)=f(n-1)+f(n-2)+f(n-3)$.

4) let $f(n)$ be the number of sequences without $011$. if the first digit is $1$ then we have $f(n-1)$ options for the other ones. if it's $0$ then we need to look at the second digit. if it's $1$ then the third digit is $0$ and after that we have $f(n-3)$ options. if it's $0$ then we are stuck because we always need to keep watching what the next digit is...I don't know how to solve it.

5) same problem as 4.

$\endgroup$
  • $\begingroup$ Your 4) is already wrong. The part of $f(n-1)$ is correct, but the latter part is wrong. You are saying that the $010$ case can be represented as $f(n-3)$, but pay attention for the fact that this does not include the $01011$ case. So far I don't have any good idea. $\endgroup$ – mathlove Dec 22 '13 at 17:06
1
$\begingroup$

1,2,3) Sounds good!

4) change perspective and consider the string from the right:

  • Ending with $0\;\,$: $f(n-1)$ possibilities for first $n-1$ digits
  • Ending with $01$: $f(n-2)$ possibilities for first $n-2$ digits
  • Ending with $11$: bad luck, all digits must be 1, so there is one case to add

All in all: $$f(n) = f(n-1)+f(n-2)+1$$

5) consider from the left again: If we start with $0$, then a sequence of zeros must be followed by a $11$. After that, we can continue as usual.

  • Starting with $1 \;\;\;\;\;$: $f(n-1)$ possibilities for last $n-1$ digits
  • Starting with $011\,\,\,$: $f(n-3)$ possibilities for last $n-3$ digits
  • Starting with $0011$: $f(n-4)$ possibilities for last $n-4$ digits
  • ...
  • Sequence is $0\dots 011$: 1 possibility
  • Sequence is $0\dots 001$: 1 possibility
  • Sequence is $0\cdots 000$: 1 possibility

All in all we get: $$f(n) = f(n-1)+\sum_{k=1}^{n-3}f(k)+3$$

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