Fibonacci Sequence Generator

Generates the first n terms of the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Each term is the sum of the two preceding ones. Variants include the Lucas sequence (different seed values) and starting from 1, 1.

For large n, the closed-form Binet's formula provides direct computation without iteration: F(n) = (φ^n − ψ^n) / √5, where φ is the golden ratio. Floating-point precision limits its accuracy beyond n ≈ 70.

The sequence is named after Leonardo of Pisa (Fibonacci), who introduced it to European mathematics in his 1202 Liber Abaci with a problem about rabbit population growth. The sequence had been documented earlier in Indian mathematics, notably by Pingala (c. 200 BCE) and Hemachandra (1150 CE), in the context of Sanskrit prosody. The "Fibonacci" attribution is European-centric; the underlying mathematics is older.

Implementation has computational implications. Naive recursion (F(n) = F(n-1) + F(n-2) with no memoization) runs in O(2^n) time because of repeated subproblem evaluation; computing F(40) takes seconds, F(50) takes minutes. Memoization or iteration produces O(n) time. Matrix exponentiation using the identity [[1,1],[1,0]]^n = [[F(n+1),F(n)],[F(n),F(n-1)]] yields O(log n) time via fast matrix power. For very large n, this is the algorithm of choice. Binet's formula is O(1) but limited by floating-point precision; F(70) is the practical ceiling in IEEE 754 double precision.

A worked example: F(50). Naive recursion takes ~12 seconds. Iterative: ~1 microsecond. Matrix exponentiation: ~1 microsecond at this scale, but pulls ahead at F(10000). Binet: produces 12586269025 with floating-point error of about 1 in the unit's place by this point. Arbitrary-precision arithmetic libraries (Python's int, Java's BigInteger) are required because F(50) = 12,586,269,025 already exceeds 32-bit unsigned integer range; F(100) exceeds 64-bit range.

The sequence connects to the golden ratio φ ≈ 1.618 through the limit F(n+1)/F(n) → φ. This emerges from any second-order linear recurrence with the same coefficients; the convergence is exponential and reaches IEEE 754 double precision by around the 37th term. Binet's formula expresses F(n) directly in terms of φ and its conjugate ψ = 1 − φ, which is the second root of x² = x + 1.

Limitations: the sequence's appearance "in nature" is overstated in popular accounts. Sunflower seed spirals and pinecone scales do follow Fibonacci-related arrangements due to optimal packing under exponential growth, but many alleged occurrences (nautilus shells, human body proportions, classical architecture) are approximate at best and sometimes invented. The sequence is mathematically interesting; its mystical reputation is not warranted by the evidence.