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?

  • $\begingroup$ Did you mean "no two 1's" can be side by side instead? $\endgroup$ – Yiyuan Lee Mar 20 '14 at 16:26
  • $\begingroup$ @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 $\endgroup$ – happymath Mar 20 '14 at 16:30
  • $\begingroup$ @Tamim Ad Dari after this induction is enough to prove it $\endgroup$ – happymath Mar 20 '14 at 16:32
  • $\begingroup$ I only find 7 for the next one... Can you check? $\endgroup$ – user88595 Mar 20 '14 at 16:33
  • $\begingroup$ @user88595: there are $8$. Take all the $5$ digit ones and append $0$ and all the $4$ digit ones and append $01$ $\endgroup$ – 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!

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.