Fibonacci sequence and Golden Ratio

Baby rabbits by Wee Gan Peng @iStockphoto

I haven’t written a math-related article in a while, so in this article, I’ll tell you about the Fibonacci sequence, the golden ratio and some associated program code.

Say you’re given this math formula, and told to find what the nth term is.
F(n) = F(n-1) + F(n-2)
where F(1) = F(2) = 1

Wow, initial conditions are given, a formula is given. Functions! In fact, use recursive functions! That was easy to code, wasn’t it?

What if you’re given this sequence of numbers and told to find what the nth term is?
1,1,2,3,5,8,13,21 …

You would get exactly the same answer for both questions. Notice that each subsequent number is a sum of the previous two numbers (except the first two in the sequence). Once you find the pattern, you can make use of simple loops instead of recursive functions. Generally speaking, recursive functions are slower, and you would not have known the simpler loop solution if you hadn’t analysed the problem first.

Of course, if you knew the numbers form the Fibonacci sequence, you wouldn’t have much of a problem in the first place, would you? You might have heard of it in Da Vinci Code, where the sequence was used to decipher a password number.

Now, the interesting thing about this sequence is that Nature uses it. I haven’t personally verified this, but sunflowers, pineapples and daisies exhibit the use. If you count the number of bumps on them going to the left, and the number of bumps to the right, you’ll find that the numbers are right next to each other in the Fibonacci sequence. For example, sunflowers have 34 spirals to the left and 55 to the right.

The rabbits, man do they breed!

There’s actually a story about how the Fibonacci sequence came about. You might have guessed that Fibonacci is the name of a mathematician. Anyway, the story goes like this. Suppose there are 2 rabbits, one male and one female. Each month, they produce two rabbits, again, one male and one female. The baby rabbits take one month to grow, and become sexually reproductive in their second month. In this manner, how many rabbits are there at the end of 12 months?

In the first month, there are 2.
At the end of the second month, there’s 4 (2 original, 2 babies).
At the end of the third month, there’s 6 (2 original, 2 from 2nd month, 2 babies from original).

At the end of the fourth month, there’s the original 2, the 2 from 2nd month, the 2 from 3rd month, 2 babies from the original 2, and 2 babies from the 2 of the 2nd month. Total rabbits: 10.

Just typing this out is confusing, but you can see a pattern emerging.
2, 4, 6, 10 …
Each subsequent term is a sum of the previous two terms.

Oh yes, the number of rabbits in the 12th month is 466.

Some obvious assumptions are

  • Rabbits never die
  • Babies are always produced in a pair, one male and one female
  • Moral values are not considered (incest shmincest!)

The golden ratio

There is another interesting thing. The ratio of F(n+1)/F(n) approaches a limit as n goes to infinity, which is approximately 1.618. This number is known as the golden ratio, with other names such as golden mean, divine proportion and others. Other than its mathematical relevance, I know it to be important as an aesthetic factor.

A rectangle with its sides in this ratio is thought of as aesthetically pleasing. This probably influenced the manufacture of computer screens. You have your standard 4:3s (1.333:1), the 800×600, 1024×768 and others. There are also some who tried the square root 2 ratio, 1.414:1 in computer applications. Then there’s the 16:9 (1.777:1) aspect ratios.

What’s the purpose of these aspect ratios? To approach the golden ratio 1.618:1. Of course, with widescreens, this point is probably moot nowadays. Still, it makes for interesting contemplation.

Ok, let’s do some coding, calculating the nth term using a loop, which I’ve hardcoded as 20. I’ll leave it to you as an exercise to write it as a function. The golden ratio is calculated as well. The first 2 terms are skipped, because they are equal to 1 (initial conditions).

int i;
int current, previous, next;
double phi = 0;
current = previous = 1;
for (i = 2; i < 20; ++i)
{
    next = current + previous;
    previous = current;
    current = next;
    phi = (double)current/(double)previous;
    Console.WriteLine("Term {0,0:d2} = {1,0:d5}, Phi = {2,0:f8}", i + 1, current, phi);
}

Fairly simple. The point is to convert a problem into a program solution. The difficult part isn’t the original problem, nor is it about coding skills. It’s about translating a problem into a program that’s difficult.

There you have it. Math theory and supporting program code. Hope you enjoyed it.

Update: Commenter Patrick pointed out the existence of the closed-form expression of the Fibonacci numbers. Thanks Patrick!

  1. Anonymous

    after 12 months there would be 144 rabbits not 466. if you find the 12th number of the fibonacci sequrnce then this is proved

  2. Vincent Tan

    Anonymous, 144 rabbits at the end of 12 months assume that the Fibonacci ruling starts at 1, as in
    1,1,2,3,5,8,13,21,34,55,89,144

    The rabbit example makes use of the Fibonacci algorithm, not the usual Fibonacci sequence. So it’s
    2,4,6,10,16,26,42,68,110,178,288,466

    Besides, there’s a flaw with the sequence you’re proposing… the rabbit population cannot spawn from just one rabbit. Thanks for pointing it out though!

  3. Patrick Cox

    Reading through your post, I expected to also see the closed form solution for the Fibonacci sequence. The cool thing is that it uses the golden ratio.

    F(n) = ((phi)^n-(1-phi)^n)/sqrt(5)

    Where phi=(1+sqrt(5))/2 a.k.a. the Golden Ratio and F(n) is the nth term in the Fibonacci sequence.

  4. Vincent Tan

    Thanks Patrick for the closed form solution. I was focused on the iterative programmatic approach, and I left that out.

  5. Vincent

    There’s not much to say for a closed form solution, kb. Check the Wikipedia page for the formula.
    http://en.wikipedia.org/wiki/Fibonacci_number

    I was calculating phi, so it doesn’t make sense to use a closed form solution which needs phi. Besides, Patrick already gave the closed form solution above.

    Hint: You’ll need the Math.Pow() and Math.Sqrt() functions in C#.

Comments are closed.