# 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

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$.

• "Then the next entry must be $1$, and the last must be $0$" Should be "and the last must be $1$" – leonbloy Jun 19 '14 at 13:44
• Thank you for spotting it! Fixed. – André Nicolas Jun 19 '14 at 15:30
• +1. "turns out that the $g_n$ are just the Fibonacci numbers". How could this be proved? – Alaa M. May 14 '16 at 17:51
• The recurrence is the Fibonacci recurrence, and the initial terms $g_0$ and $g_1$ are consecutive Fibonacci numbers, starting with the "first" Fibonacci number $1$. Note that I did not say that the sequence is the Fibonacci sequence, since that one goes $1,1,2,3,5,\dots$, so it starts with two $1$'s. – André Nicolas May 14 '16 at 17:59

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).$$

• The sequences can end in $0$, provided that they begin with $1$. – ajotatxe Jun 19 '14 at 11:44
• ahh sorry I misread – Pavan Sangha Jun 19 '14 at 11:45

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).$