binary strings and counting sequence problem

Question

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?

Answer 1

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

Answer 2

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.