For each positive integer $n$, let $a_{n}$ be the number of binary sequences of length $n$ which do not contain the sub-sequence '011'. Find a recurrence relation for $a_{n}$ and determine the initial condition.
$a_{1}$ = 2
$a_{2}$ = 4
How do I proceed from here?
$a_n=$ number of strings that starts with '$00$'.
$b_n=$ number of strings that starts with '$01$'.
$c_n=$ number of strings that starts with '$10$'.
$d_n=$ number of strings that starts with '$11$'. $$\\$$ Then,
$a_{n+1}=a_n+b_n$ (attach '$0$' in front of $a_n$ or $b_n$).
$b_{n+1}=c_n$ (attach '$0$' in front of $c_n$ [but not $d_n$]).
$c_{n+1}=a_n+b_n$ (attach '$1$' in front of $a_n$ or $b_n$).
$d_{n+1}=c_n+d_n$ (attach '$1$' in front of $c_n$ or $d_n$).
$s_{n+1}=a_{n+1}+b_{n+1}+c_{n+1}+d_{n+1}=2\cdot s_n - d_n$.