Question

A bit string is called legitimate if it contains no consecutive zeros, e.g., 0101110 is legitimate, whereas 10100111 is not. Let an denote
the number of legitimate bit strings of length n. Dene a0 = 1. Derive a recurrence relation for an (i.e., express an in terms of the preceding a_i's).

Answer 1

1. $n$ length bit strings can end with $0$ or $1$
2. We can always patch one $1$ to the end of all $n-1$ length strings of the required type.
3. Therefore no. of $n$ length bit strings that do not contain consecutive zeros and which ends with $1$ is equal to $a_{n-1}$ where $a_{n-1}$ = $n-1$ length bit strings that do not contain consecutive zeros.
4. We can also patch one $0$ at the end of all such $n-1$ length strings which do not contain consecutive zeros and that ends with $1$.
5. In point $3$ we have just derived that, $a_{n-1}$ = $n$ length strings that do not contain consecutive zeros and ends with $1$. So, therefore, To satisfy point $4$, we have, no of $n$ length bit strings that do not contain consecutive zeros and that ends wth $0$ = no of $n-1$ length bit strings that do not contain consecutive zeros and that ends wth $1$ = $a_{n-2}$  
6. There is no other possibility of ending a string other than with $0/1$ and there are no overlapping cases.
7. Therefore final recurrence relation : $a_n = a_{n-1} + a_{n-2}$

Answer 2

It is simply fibonacci series, with basis

a₀=1 & a₁=2

Then a_n=a_n-1+a_n-2

a₁=2 can be derived by enumeration only 2 single length binary string can be form and because its length is 1 so no consecutive 0's