Finite bit strings that do not contain '$00$'

Question

I am studying for an exam and I am having trouble with this practice question:

In this question, we consider finite bit strings that do not contain $00$. Examples of such bitstrings are $0101010101$ and $11110111$. For any integer $n\geq 2$, let $B_n$ be the number of bitstrings of length $n$ that do not contain $00$.

• Determine $B_2$ and $B_3$.
• Prove that $B_n = B_{n-1} + B_{n-2}$ for each $n\geq 4$.
• For each $n\geq 2$, express $B_n$ in terms of a Fibonacci number.

Any help is greatly appreciated

Answer 1

$\textbf{Hint:}$The first question can be answered by simply counting. For the second question note that every bitstring without $00$ ends in either $1$ or in $10$. How many possibilities are there in either case? The third question can be answered by combining the results of the first two questions.

Answer 2

HINT: Suppose we have a bit string of length $n$. Consider the first digit of this bit string:

If the first digit is $1$, i.e. we have $1xxxxxxxxxxxxx\ldots$ as our bit string. How many possibilities are there for the remaining $n-1$ digits?

If the first digit is $0$, what $\mathbf{must}$ the next digit be? What are the possibilities for the remaining $n-2$ digits?