I’m guessing that all my blog readers know what the Fibonacci sequence is. For the uninitiated, it is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…. ad infinitum.

Each number is the sum of the preceding 2 numbers. That is,

F(n) = F(n-1) + F(n-2)

where,

F(0) = 0

F(1) = 1

A Neat Trick:

————-

How can you easily convert miles to kilometers? You can use Fibonacci numbers: 5 miles is 8 kilometers (actually 8.045 km). 8 miles is 13 kilometers (12.87 km). 13 miles is, yes you guessed it, 21 kilometers (20.917 km). “But hey, this will only work for Fibonacci numbers!”. Well, I’m not done yet! Say you want to convert 20 miles to kilometers. Simply express 20 as the sum of Fibonacci numbers:

20 = 13 + 5 + 2.

Convert each number according to our mile-kilometer rule:

= 21 + 8 + 3

= 32

Voila! In actuality, 20 miles comes to 32.18 km. Neat huh?

Can you guess the logic behind this? The reason this works is as follows:

To convert from miles to kilometers, we have to multiply by a factor of 1.609. Now, the Fibonacci sequence has an extremely interesting property – the ratio of two consecutive Fibonacci numbers approaches the Golden Ratio: 1.618. Mystery solved!

A Puzzle:

———

Now here is a question I was once asked:

“For a flight of stairs with n steps, write a program to print the number of ways you can climb it if you can only move either one or two steps forward at any point.”

I couldn’t figure it out in time, but understood the approach later (I think Prajwalit was the one who told me the answer). Since this post is about Fibonacci numbers, it’s a given that they make an appearance in this puzzle. The challenge is to explain why the Fibonacci numbers show up.

Finally, for a tougher programmatic challenge, modify the problem as follows:

“For a flight of stairs with n steps, write a program to print all the combinations of ways you can climb it if you can only move either one or two steps forward at any point. If n is entered as 3, your program should show the following output –

n = 3

1 1 1

1 2

2 1”

### Like this:

Like Loading...

*Related*

Tags: Math, Puzzles

This entry was posted on January 21, 2010 at 3:09 pm and is filed under Geek Stuff. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 22, 2010 at 4:11 am |

this is great… I used to use the ratio 1 mile = 2 km 🙂 now that I think of it I think i was confused in pounds vs kgs n kms vs miles ratio 😛

January 22, 2010 at 9:03 am |

Good read 4 newbies. One can read wikipedia post abt it.

Myself, I remembered d books wid subject as mathematical magic read in childhood & reference in Da Vinci Code.

January 22, 2010 at 1:00 pm |

Social comments and analytics for this post…This post was mentioned on Twitter by abhijitvaidya: Fibonacci Numbers http://bit.ly/8AwaqP…

January 23, 2010 at 6:54 am |

Its pretty straightforward to explain why the fibonacci numbers show up in that puzzle.

Here’s why:

Suppose you have a flight of n stairs. Now, the last step you take can either be 1 stair or two stairs.

Case 1) Last step = 1 stair

For this case, the total number of ways to climb n stairs = total number of ways to climb (n-1) stairs = F(n-1)

Case 2) Last step = 2 stairs

Total number of ways to climb n stairs = Total number of ways to climb (n-2) stairs = F(n-2)

Combining case 1 and case 2,

F(n) = F(n-1) + F(n-2)

which is the fibonacci series.

March 22, 2010 at 6:03 am |

[…] post, वेदांग मणेरीकर द्वारा प्रकाशित Fibonacci Numbers या लेखाचे भाषांतर असून, https://mytechrants.wordpress.com […]

May 27, 2010 at 6:13 pm |

int steps(int n)

{

int count;

if(n == 0)

return 0;

else if((n == 1) || (n == 2))

{

return 1;

}

count = steps(n-1) + steps(n-2);

return count;

}

hope this helps

May 27, 2010 at 6:43 pm |

int steps(int n)

{

int count;

if(n == 0)

{

return 0;

}

else if((n == 1))

{

return 1;

}

else if(n == 2)

{

return 2;

}

count = steps(n-1) + steps(n-2);

return count;

}

May 27, 2010 at 6:43 pm |

can anybody help me with printing the combinations?

that is if n is entered as 3, your program should show the following output –

n = 3

1 1 1

1 2

2 1″

February 22, 2012 at 9:26 pm |

Who Assinates the Assasin…[…]Fibonacci Numbers « Tech Rants[…]…

April 10, 2012 at 4:56 pm |

kalkulator zdolności kredytowej…[…]Fibonacci Numbers « Tech Rants[…]…