Get a recurrence relation for the number of binary string that do not contain exactly two 0s in a row. (As example, 010000 is acceptable, but 10011000 is not acceptable)
My approach: I know that $2^n$ ways for length n, and I know that C(n, 2) ways to contains exactly two 0s, but I don't understand how I can ensure that it does not happen in a row with the term "exactly".
$$a_n=a_{n-1}+a_{n-2}$$ with $a_1=2$ and $a_2=3$. This is because every valid string of length $n$ either starts with a $1$ then proceeds with a valid string of length $(n-1)$ or starts with $01$ then proceeds with a valid string of length $(n-2)$.
This gives us the closed form $a_n=F_{n+2}$ where $F_n$ denotes the $n$th Fibonacci number.