Explicit Fibber

The nth number of the fibonacci sequence is defined as F(n) = F(n-1) + F(n-2) for n > 1, and n for n <= 1.

This is a recursive definition, i.e. the result of F(n) depends on itself.1

Then some guy, Jacques Philippe Marie Binet, did something cool. He, through some mathematical wizardry, found the ‘explicit’ formula, i.e. non-recursive. And it goes like this:

F(n) = \frac{(1+\sqrt{5})^n -(1-\sqrt{5})^n}{2^n\sqrt{5}}

  1. Unless n is less than or equal to 1.