The Fibonacci numbers are a sequence of numbers generated by a simple rule – you start with the pair of numbers (0,1), and to get the next term, you add the previous 2 terms. The sequence looks a little something like this:
if you keep following this rule, you end up with something like this:
1,1,2,3,5,8,13,21,34,55,89… (and so on)
and so on. More generally,
Fn=Fn-1+Fn-2, for n≥2
This is the rule for the Fibonacci numbers most people would know – it’s simple, and easy to see what’s going on. However, it comes at a cost – what if you want to know, for example, what the 37,086 term was? Well, under this rule, you’d be doing a lot of adding. It’s really inefficient to calculate using this rule, known as a recursive algorithm, because it requires you to calculate all the smaller values, and work up to the larger one.
So, is it possible to make an algorithm that lets you go straight to the nth Fibonacci number? As it turns out, yes, it is! And here is that algorithm.
(Note – I didn’t find this, it’s very well known as Binet’s formula!)
Where φ and ψ are (1+√ 5 )/2 and (1-√ 5 )/2 respectively. Even though both those numbers are irrational (meaning they can’t be precisely represented by any fraction), the result is always a whole number, the nth Fibonacci number. This seems like a totally random result – where on earth did it come from? In another post, I’ll explain one avenue for finding this result.