Binary sequences of lenght n, with no two consecutive zeros and if starts with zero has to end with one 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 
 A: 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$.
A: In the case of starting with a $0$
Let $A(n)$ be the number of such strings of length $n$ and suppose we know $A(k)$ for $k<n$. Now each string of length $n$ can end in a $01$ or $11$. If it ends in $01$ the number immediately before the $0$ must be a $1$ and so it must actually end in $101$ the first $n-2$ digits form a sequence $A(n-2)$. If it ends in $11$ then the first $n-1$ digits form a sequence in $A(n-1)$. It follows that $$A(n)=A(n-1)+A(n-2).$$ In other words a string on length $n$ can be obtained by amending a $01$ onto the end of a sequence of length $n-2$ or a $1$ onto a sequence of length $n-1$.
Perhaps look at something similar for strings starting with a $1$ of course there are more options. If you call this $B(n)$ your total will be $$C(n)=A(n)+B(n).$$
A: Let $B(n)$ be the number of strings starting with a $1$. Further more let $B_{1}(n)$ be the number of strings starting with a $1$ and ending in a $1$ and let $B_{0}(n)$ be the number of strings starting with a $1$ and ending in a $0$, it follows that $B(n)=B_{1}(n)+B_{0}(n)$. With a bit of calculation you can see that $B_{1}(n)=B_{0}(n-1)+B_{1}(n-1)$ and $B_{0}(n)=B_{1}(n-1).$
