## Fibonacci sequence and Golden Ratio

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!