Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.

I'm lost on how to start this.

Question

Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.

I'm lost on how to start this.

ganeshie8 · Answer

The number of $n$ bit binary strings can be thought of as two sets  :
1) Strings that end in $1$
2) Strings that end in $0$

ganeshie8 · Answer

Let $a_n$ denote the number of $n$ bit strings that do not have two consecutive 0's

ganeshie8 · Answer

If the string ends in $1$, then the $n-1$th bit could be either $0$ or $1$ so the number of $n$ bit strings that end in $1$ and do not have two consecutive $0$'s are $a_{n-1}$

|dw:1434309606750:dw|