The Fibonacci secret hidden in coding problems

Consider the question "How many binary numbers of 2 digits have no consecutive ones?"
Of course, the first solution that comes to mind is to find all the combinations of 2 digit binary numbers and then count the numbers with no consecutive ones.

All the 2 digit binary numbers are

00

01

10

11

There are 8 such numbers. Of these, the numbers with no consecutive 1's are 00, 01, 10.
So The answer in this case would be 3.

We can do this for binary numbers of 'n' digits.
For n=3 All the 3 digit binary numbers are :

000

001

010

011

100

101

110

111

There are 8 such numbers. Of these, the numbers with no consecutive 1's are 000, 001, 010, 100, 101.
So The answer in this case would be 5.

Fibonacci Method :

Finding all the combinations is a very expensive operation. If you notice closely, the answer to the above problem is nothing but the 'n+2' th digit of the Fibonacci series.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

n=2 = > 2+2 = 4'th digit of Fibonacci series = > 3
n=3 = > 3+2 = 5'th digit of Fibonacci series = > 5

Thus, we can find the answer in just O( Log n ) time.

Similar problem for practice :

Find the number of ways a wall of size 2xN can be filled with bricks of size 1x2 and 2x1 (width x height).
Here is a little diagrammatic representation of the solution : 

Here is a wonderful proof through mathematical induction I found on Stack Exchange.

Powered by Froala Editor