I need to find the number of length n binary sequences without the sequence 011. my attempt was:
Let $a_n$ be the number of good sequences of length $n$ and $b_n$ be the number of good sequences of length $n$ such that if you add a $1$ at the end it will be a bad sequence.
So $a_n = 2a_{n-1}-b_{n-1}$ becuse each sequence in $a_{n-1}$ if I add a $0$ it will be ok, if i will add $1$ it will contain all the bad sequence of $b_{n-1}$,1 so i need to subtract it
and we have $b_n = a_{n-2}$ all the good sequences adding $0,1$ at the end
so we have $a_n = 2a_{n-1}-a_{n-3}$
i tried to find a solution for the recurrence relation, i got the following equation:$x^3-2x^2+1 =(x-1)(x^2-x-1)$ so $1$ is the only root for the characteristic polynomial but how do i proceed from here?
Edit: I had a mistake with the roots.The roots of $(x^2-x-1)$ are: $x_{1,2} = (\frac{1-\sqrt{5}}{2}),(\frac{1+\sqrt{5}}{2})$
So to conculde I get:
$a_n = (1-\frac{2}{\sqrt{5}})(\frac{1-\sqrt{5}}{2})^n + (1+\frac{2}{\sqrt{5}})(\frac{1+\sqrt{5}}{2})^n -1$