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?
On
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.
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.