Find a recurrence relations and give initial conditions for the number of bit strings of length $n$ that do not have two consecutive $0$s. How many such bit strings are there of length $7$?
I go this question, and I can find out recurrence relation is : $a_n= a_{n-1} + a_{n – 2}$. But I misunderstand about how to give initial conditions for this. So could you please help me for this question.
Thanks all.
Best Answer
No string of length $1$ has two consecutive $0$, and $a_1=2^1-0=2$.
A single string of length $2$ has two consecutive $0$, and $a_2=2^2-1=3$.