Fibonacci Sequence Generator

The Fibonacci sequence is a series of numbers where each term is the sum of the two preceding terms, starting from 0 and 1. The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and continues infinitely. Named after the Italian mathematician Leonardo of Pisa (Fibonacci), who introduced it to Western mathematics in 1202 through his book Liber Abaci, the sequence actually appeared in Indian mathematics centuries earlier. The Fibonacci sequence is one of the most famous sequences in mathematics and appears in surprising places across nature, art, and technology.

The Fibonacci sequence is deeply connected to the golden ratio (phi = 1.618...), as the ratio of consecutive Fibonacci numbers converges to phi. This ratio appears in spiral patterns of sunflower seeds, pinecone scales, and seashells. In computer science, Fibonacci numbers underpin efficient algorithms like Fibonacci heaps and the analysis of the Euclidean algorithm. In financial markets, Fibonacci retracement levels are used by traders to predict support and resistance levels in stock prices.

Important properties include: (1) F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1 (recursive definition). (2) The ratio F(n+1)/F(n) approaches the golden ratio phi as n grows. (3) Every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers (Zeckendorf's theorem). (4) GCD(F(m), F(n)) = F(GCD(m,n)). (5) The sum of the first n Fibonacci numbers equals F(n+2) - 1. (6) Binet's formula gives a closed-form expression using the golden ratio.

For generating many terms, use iterative computation rather than naive recursion, which has exponential time complexity. Memoization or dynamic programming reduces this to linear time. For very large Fibonacci numbers, matrix exponentiation computes F(n) in O(log n) time. When checking if a number is Fibonacci, test whether 5n^2 + 4 or 5n^2 - 4 is a perfect square. In applications, be aware that Fibonacci numbers grow exponentially, approximately as phi^n / sqrt(5).