# binary strings and counting sequence problem

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?

• If you want to get good answers, you should tell us first what you have tried out so far? and where you have stuck? – Ehsan M. Kermani Jan 14 '15 at 6:18
• I don't understand what they mean by counting sequence (the definition seem to be vague). I tried the first one on my own. – machael Jan 14 '15 at 6:20
• 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? – Ehsan M. Kermani Jan 14 '15 at 6:23
• 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$. – 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$.