What is the number of binary sequences of length $n$, with no two consecutive zeros, and if starts with $0$ has to end with $1$.
Would appreciate suggestions and help.
I tried counting the total sequences and than substractung the ones containing 2 consecutive zeros, and then substracting the ones starting and ending with seros- but it got messy and confusing
Best Answer
Call a sequence of length $n$ good if it has no two consecutive $0$ (no other restriction).
Let $g_n$ be the number of good sequences of length $n$.
Now look at our more restricted collection, with the added condition that if we start with $0$ we must end with $1$. There are two types of such sequences of length $n$.
(i) The sequences of length $n$ that start with $1$. We can get these by taking any good sequence of length $n-1$, and putting a $1$ in front. There are therefore $g_{n-1}$ of these.
(ii) The sequences of length $n$ that start with $0$. Then the next entry must be $1$, and the last must be $1$. In between can be any good sequence of length $n-3$, so there are $g_{n-3}$ of these.
So if $a_n$ is the number of restricted condition sequences of length $n$, then $$a_n=g_{n-1}+g_{n-3}.$$
Now we go after the $g_n$, a more familiar problem. It turns out that the $g_n$ are just the Fibonacci numbers. For a good sequence of length $n$ either ends with a $1$ or a $0$. If it ends with $1$, it can be produced by appending a $1$ to a good sequence of length $n-1$. If it ends with $0$, then the previous entry (if any) must be $1$, and the part before that is any good sequence of length $n-2$. Thus $g_n=g_{n-1}+g_{n-2}$.
Now put the pieces together. Note that $g_0=1$ and $g_1=2$.