Fibonacci Numbers

by

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”

Advertisements

Tags: ,

10 Responses to “Fibonacci Numbers”

  1. Prajwalit Says:

    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 😛

  2. aDi Says:

    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.

  3. uberVU - social comments Says:

    Social comments and analytics for this post…

    This post was mentioned on Twitter by abhijitvaidya: Fibonacci Numbers http://bit.ly/8AwaqP

  4. Jitesh Says:

    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.

  5. फिबोनाकी सिरीज- Fibonacci Series - Tech News, How-To's, Events etc… - टेक मराठी -Technology बद्दल सर्व काही मराठीमधून Says:

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

  6. Kushal Dave Says:

    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

  7. Kushal Dave Says:

    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;
    }

  8. Kushal Dave Says:

    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″

  9. Who Assinates the Assasin Says:

    Who Assinates the Assasin…

    […]Fibonacci Numbers « Tech Rants[…]…

  10. kalkulator zdolności kredytowej Says:

    kalkulator zdolności kredytowej…

    […]Fibonacci Numbers « Tech Rants[…]…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: