Let $B_n$ be the set of binary strings of length $n$ such that:
Every even length block of $0's$ is followed exactly by $1$, and
Every odd length block of $0's$ is followed exactly by $11$ (exactly two 1's)
and a block is a substring of non-zero length of either $0's$ or $1's$.
Let $b_n$ be the cardinality of $B_n$. How can I show that $$b_n=b_{n-2}+2b_{n-3}$$ where $b_0=b_1=b_2=1$ and $b_3=3$.
I tried to come up with the sets $B_3$ and $B_5$ which are $$B_3=\{001,011,101\}$$ and $$B_5=\{00101,10101,11001,11011,11101\}.$$ I know I have to use rule of sum (and/or maybe bijection) but I am having some troubles defining the sets by looking at the trivial case that I found. Any help on how to show this recurrence will be highly appreciated
I think the argument for the recurrence assumes the string must start with $0$. Then an acceptable string of length $n$ can come from a string of length $n-2$ which you put $00$ in front of or a string of length $n-3$ that you put $001$ or $011$ in front of. That gives the recurrence $b_n=b_{n-2}+2b_{n-3}$ with $$B_3=\{001,011\}\\ B_4=\emptyset\\B_5=\{00001,00011\}\\ B_6=\{001001,001011,011001,011011\}$$