Sunday, July 01, 2012

Adventures in Fibonacci Numbers

You may remember the Fibonacci numbers from math class. The Fibonacci sequence of numbers is easy to generate: begin with 0, 1. Then add the two previous numbers to get the next number in the sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
If you take the ratio of consecutive numbers in the sequence, you can see an interesting pattern:
0, 1, 0.5, 0.667, 0.6, 0.625, 0.615, 0.619, 0.6176, 0.61818, 0.617977, 0.618056...
Graphing these numbers, we can see that they seem to be honing in to one number -- increasingly accurate lower and upper bounds to a number that turns out to be roughly 0.61803, or more exactly 2/(sqrt(5)+1), the reciprocal of the Golden Ratio.

(In the above graph, I cut out the first few ratios so we could see the trend better.)

There are a lot of cool applications to for the Fibonacci sequence. It is often found in nature -- for example, the arrangement of seeds in a sunflower head, or the unfurling of a fern. There are also computer science data storage techniques, such as Fibonacci heap, that are derived from the sequence.

But a really cool use of Fibonacci numbers that I learned recently is the conversion between miles and kilometers. As it turns out, the ratio of miles to kilometers (0.621371192 mi/km) is pretty close to the ratio to which sequential Fibonacci numbers converge (0.61803), so we can use the sequence of Fibonacci numbers to roughly convert from miles to kilometers and vice versa. If we want to convert 3 miles to kilometers, for example, we simply take the next number in the Fibonacci sequence, so 3 miles is about 5 kilometers. (Doing the actual math, it's 4.828, which is pretty close.) Similarly, if we want to convert 13 kilometers to miles, then we take the previous number in the Fibonacci sequence, so 13 km is about 8 miles. (Again, doing the actual math, we obtain 8.078, so not bad!)

If you have a number that is not in the Fibonacci sequence, you can simply break it down into two Fibonacci numbers (there's a theorem that says you can do that for any integer!), and do the conversion on those two numbers and add the results back together. So, if you want to know what 60 miles is in kilometers, you break down 60 into 5 + 55, and convert them both to kilometers, so 8 + 89, to obtain an answer of 97 km. The actual answer is 96.56 km, so not too bad!

I plan to use this handy conversion factor in Australia to help me transition into understanding distance in kilometers. But also because it is just about the coolest thing I have seen in a long time!


Unknown said...

Holy Crud! This is probably the best thing I'll read all month. You may not know it, but the Fibonacci sequence is my most favorite sequence!

I plan on using this whenever possible.

Jenny F. Scientist, PhD said...

I always found the mental conversion of KPH to MPH the hardest (how fast am I really going?) - probably because one must, of necessity, do it while driving. Handy trick!

Common Household Mom said...

This is new and interesting info to me about the Fibonacci series. Thanks!

outofthenormaths said...

I've long loved this conversion, but have only just seen the extension to non-Fibonacci numbers.

One correction, there isn't a theorem that says any number is the sum of two Fibonacci numbers. For example, 12 isn't.

But the 'Zeckendorff representation' allows you to write any number in a unique way as the sum of non-adjacent Fibonacci numbers. So 12 = 8 + 3 + 1 (skips 5 & 2). Then you can use that if you want to be exact in your approximation.

Eg. see here:

Rebecca said...

Thanks for the correction! I knew you could write any integer as the sum of Fibonacci numbers, but I obviously made up the part about it being only two ;)

Kevin said...

I was at a talk George Andrews gave to the math club in Urbana around 1998 (plus or minus 2 years), and he introduced this. If I recall correctly, he took credit for it, and there may have been some inspiration on the back of a cereal box. Don't quote me on that last sentence, though.