Find a recurrence relation for the number of bit strings of length ݊that do not have two consecutive 0s.

Question

I've found this problem in "Discrete Mathematics and Application" by Kenneth Rosen. I also found an explanation of the way of solving this problem which goes like that,

Case 1: Start with a 1 – how many are these? If we remove the 1, then these strings are just the number of such strings of ܽa_n-1. Why? Because if you remove the 1, then all these strings must make the set ofܽ a_n - 1, i.e., strings of length ݊ − 1 that do not have two consecutive 0s.

Case 2: Start with a 0 – how many are these? These strings must also have a 1 at the second position. The number of such strings is ܽa_n-2. Why? Because if remove the last two digits “10”, these strings must make the set of ܽa_n-2, i.e., strings of length ݊n − 2 that do not have two consecutive 0s.

But i found it too complex, can anyone please make this a little bit easier ?

Answer 1

Let $a_{n}$ denote the number of strings of length $n$ that do not have consecutive $0$'s.
CASE $1$: Number of strings of length $n$ ending with $1$ is $a_{n-1}$.
CASE $2$: Number of strings of length $n$ ending with $10$ is $a_{n-2}$.
This yields the recurrence relation

$$a_{n} = a_{n-1} +a_{n-2}$$ for $$n\geq 3$$ where $a_{1}=1,a_{2}=3$.