What is the relation between this binary number with no two 1 side by side and fibonacci sequence?

I saw this pattern of binary numbers with constraints first number should be 1 , and two 1's cannot be side by side. Now as an example

1 = 1
10 = 1
100,101 = 2
1000,1001,1010 = 3
10000,10001, 10010, 10100, 10101 = 5

Strangely I see the numbers we can form of this binary numbers with $n$digit is the$n$th Fibonacci number , at least for for the first 5 Fibonacci number. How Can we show that it is true for nth number ? and how is this happening?

• Did you mean "no two 1's" can be side by side instead? – Yiyuan Lee Mar 20 '14 at 16:26
• @Tamim Ad Dari if you observe the numbers which have 1 at the end are also forming a fibonacci sequence after n>2 same with zeros – happymath Mar 20 '14 at 16:30
• @Tamim Ad Dari after this induction is enough to prove it – happymath Mar 20 '14 at 16:32
• I only find 7 for the next one... Can you check? – user88595 Mar 20 '14 at 16:33
• @user88595: there are $8$. Take all the $5$ digit ones and append $0$ and all the $4$ digit ones and append $01$ – Ross Millikan Mar 20 '14 at 16:35

Suppose we make an $n$-digit string with no consecutive $1$s. Then it either ends with a $0$ or a $1$.
If it ends with a $0$, we can add (from the front) any $(n-1)$ digit string with no consecutive $1$s. There are $a_{n-1}$ of these.
If it ends with a $1$, then the previous digit must be a $0$ because there are no consecutive $1$s. But before this $1$ we can add any $(n-2)$-digit string. There are therefore $a_{n-2}$ $n$-digit strings with no consecutive $1$'s which start with $10$.
Hence $a_n = a_{n-1} + a_{n-2}$. This is exactly the Fibonacci sequence!
It's well known (and easy to prove) that the Fibonacci numbers give the number of ways you can tile a $1\times n$ strip with $1\times1$ squares and $1\times2$ dominoes -- see, for example, the introductory section of this paper by Benjamin, Quinn, and Su. Ignoring, the initial $1$ in your binary numbers, everything that follows can be interpreted as a string of squares, each with a $0$ written on them, and dominoes, each with a $01$ (in that order), written on them.