Disclaimer: This is a school assignment so please don't give me the answer right away.
Let $S$ be the set of binary strings where any block of $0$'s must be followed by a block of $1$'s of greater length, and let $a_{n}$ be the number of strings in $S$ of length $n$. Prove that for $n\geq1, a_{n}=f_{n}$ where $\{f_{n}\}$ is the Fibonacci sequence. (Hint: Use the set $M=\{01,0011, 0000111,...\}$, and modify the block decomposition.
I am having trouble to even start the question, especially the "let $a_{n}$ be the number of strings in $S$ of length $n$".
Can someone lead by just giving me some examples of $a_{n}$? Any help is much appreciated. Thanks!
To get you started, here are the qualifying strings in $S$ for some low values of $n$:
\begin{array}{r|c|c} n=1 & 2& 3 & 4 & 5\\ \hline 1 & 11 & 111 & 1111 & 11111 \\ & & 011 & 1011 & 11011\\ & & & 0111 & 10111\\ & & & & 01111 \\ & & & & 00111 \\ \end{array}
I have ordered the sets in a way that might be helpful...