2
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "Then the next entry must be $1$, and the last must be $0$" Should be "and the last must be $1$" $\endgroup$ – leonbloy Jun 19 '14 at 13:44
  • $\begingroup$ Thank you for spotting it! Fixed. $\endgroup$ – André Nicolas Jun 19 '14 at 15:30
  • $\begingroup$ +1. "turns out that the $g_n$ are just the Fibonacci numbers". How could this be proved? $\endgroup$ – Alaa M. May 14 '16 at 17:51
  • $\begingroup$ 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. $\endgroup$ – André Nicolas May 14 '16 at 17:59
0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.