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?

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!
In fact, this is the very explanation (with some modification) Derek Holton gave in his wonderful book - A Second Step to Mathematical Olympiad Problems, for a similar problem.
