What is the number of binary sequences of length N in which every occurrence of zeros has even length?

Question

In my understanding, I need to generate some kind of regular expression, which can describe all the possible sequences, such as:

00
1
0000
0000111100
...

But I can't understand how it should look like.

Answer 1

Let's call $a_n$ the number of such sequences of length $n$.

Consider a generic sequence with the given property, it can either start with a $1$ or with two $0$.

In the first case there are $a_{n-1}$ sequences (why?) and in the second one $a_{n-2}$ (why?). So $a_n = a_{n-1} + a_{n-2}$ for any $n \geq 3$.

But $a_1 = 1$ and $a_2 = 2$. Then $a_n = F_{n+1}$ where $F_{n}$ is the $n$th Fibonacci number