Why are bitstrings without 00 of length n equals $Fib_{n+2}$?

Question

EDIT: $B_{n}$ denotes the number of bitstrings of length n without 00.

So I've been studying Discrete Math, and I came across the proof that $B_{n} = f_{n+2}$. What I do not understand about this is, why is it equal to the (n+2)th fib series? The book explains it in terms of matrices and tbh I don't quite understand it.

I tried counting $B_{4}$ and it was a equal to 8, which is $B_{1} + B_{2}$.

What I understood so far is, to build a bitstring of length n, you first need to know the bitstring of length n-1, and all the way until 1. So following that, a bitstring of length n (any bitstring), is equal to all combinations of bitstring n - 1 * 2, right? (Because you either add 1 or 0 in the last digit).

Is it the same of bistrings without 00? (although when I tried that, you had to make sure the combination of any two bistrings do not end and start with 0)

Answer 1

To find the binary strings of length $n+1$ with no $00$ substring, you can either take a string with this property of length $n-1$ and add $10$ to the end, or you can take a string with this property of length $n$ and add $1$ to the end.

Answer 2

Let $X_{n}$ be the number of bit strings of length n with no 00 that end in zero, and $Y_{n}$ be those that end in one.

Clearly $X_{1}$ and $Y_{1}$ are both 1.

Suppose we know $X_{k}$ and $Y_{k}$ and we wish to know $X_{k+1}$ and $Y_{k+1}$. Do you see why

$X_{k+1}$ = $Y_{k}$

$Y_{k+1}$ = $X_{k}$ + $Y_{k}$

?

Can you take the proof from here?