Fibonacci N-ésimo

The n-th Fibonacci number

The Fibonacci sequence starts from F(0) = 0, F(1) = 1, and from there F(n) = F(n−1) + F(n−2) for n ≥ 2. Getting just the n-th term, without writing out everything before it, turns out to be a textbook problem in algorithms. There's a closed form, Binet's formula: F(n) = (φⁿ − ψⁿ) / √5, where φ = (1+√5)/2 ≈ 1.6180 and ψ = (1−√5)/2. So F(10) = (φ¹⁰ − ψ¹⁰)/√5 = 55. How do the algorithms compare? Naive recursion is O(2ⁿ), exponential because it keeps redoing the same subproblems. Add memoization to the top-down version and you drop to O(n). The iterative two-variable loop is also O(n), but with O(1) memory. Binet runs in O(1) yet starts drifting due to floating-point error past n > 70. And matrix exponentiation with [[1,1],[1,0]]ⁿ brings it down to O(log n).

Applications

You'll find F(n) in nature, from phyllotaxis to the spirals on sunflowers and pinecones. It shows up in art and architecture too, like Le Corbusier's Modulor, and in market technical analysis, where traders watch Fibonacci retracements at 23.6%, 38.2% and 61.8%. Computer-science courses lean on it as well, using it to teach recursion and dynamic programming.

FAQ

Why doesn't Binet work for very large n? Floating-point math runs out of precision. Somewhere around n > 70 the answer it gives no longer matches the exact integer Fibonacci value.

Which algorithm is fastest in practice? When n is moderate, say up to a few thousand, the iterative O(n) version is the simplest and already plenty fast. Once n gets huge, matrix exponentiation O(log n) pulls ahead.

Does the index start at 0 or 1? These days the standard is F(0) = 0, F(1) = 1. You'll still run into older books that write F(1) = F(2) = 1, which shifts every index by one.