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?