Recurrence relations - simple questions, please verify my answers.

Question

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.

Answer 1

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