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