Hello i'm working on these questions and I have few questions

1) A binary string is a finite sequence of 0 and 1. Ex. 001101 is a string of length 6 a) List all binary strings of length 4 (so I assume 2^4 = 16.)

2) List all binary strings of size at most 6 which do not have two consecutive 0s. Using this list give the beginning of the counting sequence for binary strings with no consecutive 0s. Can you see the pattern? ( Im not sure how binary string can be size 6. Maybe for example 000011 like this?

  • $\begingroup$ If you want to get good answers, you should tell us first what you have tried out so far? and where you have stuck? $\endgroup$ – Ehsan M. Kermani Jan 14 '15 at 6:18
  • $\begingroup$ I don't understand what they mean by counting sequence (the definition seem to be vague). I tried the first one on my own. $\endgroup$ – machael Jan 14 '15 at 6:20
  • $\begingroup$ Ok, 1) is correct. Note that there are $2$ choices for each place $0$ or $1$ and there are three places you should fill in, so there are $2^3=8$ binary sequences of length $3$ as you wrote. Can you generalize this to answer 2, 3? $\endgroup$ – Ehsan M. Kermani Jan 14 '15 at 6:23
  • $\begingroup$ If you make a careful list, or use some theory, you will find that the number of binary sequences of length $k$ with no two consecutive $0$'s is equal to $2,3,5,8,13,21$ for $k=1,2,3,4,5,6$. $\endgroup$ – André Nicolas Jan 14 '15 at 6:25

If $s$ is an admissible string (i.e., has no two consecutive zeros) then any initial segement $s'$ of $s$ is admissible as well.

Denote by $A_n$ the set of admissible strings of length $n$, and put $a_n:=\#A_n$ $(n\geq0)$. One has $A_0=\{\Lambda\}$ (the empty string), $A_1=\{0,1\}$. Now let an $n\geq2$ be given, and consider an $s\in A_n$. If $s=s'1$ then $s'\in A_{n-1}$, with no further conditions on $s'$. If $s=s'0$ then necessarily $s=s''10$ with $s''\in A_{n-2}$, and no further conditions on $s''$.

We therefore have $$a_n=a_{n-1}+a_{n-2}\qquad(n\geq2)\ .$$ This allows to conclude that for all $n\geq0$ one has $a_n=F_{n+2}$ (Fibonnacci number, whereby $F_0=0$).


Typically, in this sort of context, a "counting sequence" is the sequence $(a_n)_{n\in\mathbb{N}}$ where for $n\in\mathbb{N}$, $a_n$ is the number of objects under consideration which have size exactly $n$.

So, what question two is basically asking you to do is given $n$, find a formula (in terms of $n$) for the number of binary sequences of length exactly $n$.

For question (3): Yes, your interpretation is correct.


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.