Each term is the sum of the two before. Despite the simplicity of the rule, the sequence has profound connections to algebra, geometry, number theory, and the natural world.
Historical origin. Named after Leonardo Fibonacci of Pisa, who introduced the sequence to Western mathematics in his 1202 book Liber Abaci through a problem about rabbit populations. The sequence was known earlier in Indian mathematics, particularly in Sanskrit prosody.
Index conventions. This explorer uses F1=F2=1. Other conventions start at F0=0,F1=1 (giving the same sequence shifted by one). Be careful when comparing references.
Exact computation. Fibonacci numbers grow exponentially — F100 has 21 digits, F1000 has 209 digits. The explorer uses arbitrary-precision integers (BigInt) so every term is exact at any index, with no floating-point error.
For deeper coverage see Fibonacci sequence, golden ratio, and linear recurrence.
The Recurrence and Binet's Formula
The recurrence.Fn=Fn−1+Fn−2 is a second-order linear recurrence with constant coefficients. Its characteristic equation is
x2=x+1
with roots
φ=21+5≈1.61803398…,ψ=21−5≈−0.61803398…
φ is the golden ratio.
Binet's formula. The closed-form expression for Fn is
Fn=5φn−ψn
Since ∣ψ∣<1, ψn shrinks rapidly to zero, and Fn is well-approximated by φn/5 for large n.
Why the formula gives an integer.φ and ψ are irrational, but the combination φn−ψn always lies in 5Z — the difference of conjugate irrational powers cancels into a rational multiple of 5. Dividing by 5 gives an integer.
Practical computation. Binet's formula has floating-point limitations: for large n, the formula needs more precision than typical doubles provide. The recurrence (or matrix exponentiation, or fast doubling) is preferred for exact computation, which is why this explorer uses BigInt iteration.
Matrix form.(Fn+1Fn)=(1110)n(10). Matrix exponentiation by repeated squaring computes Fn in O(logn) multiplications.
The Membership Test — Gessel's Identity
Given a positive integer m, how do you decide whether m is a Fibonacci number?
Gessel's identity (1972).m is a Fibonacci number if and only if
5m2+4or5m2−4
is a perfect square. Once one of these is a perfect square, the index n is found by iterating the Fibonacci recurrence until Fn=m.
Why two cases. The identity has both +4 and −4 because Fibonacci numbers at even and odd indexes behave differently with respect to the underlying Lucas-Fibonacci identity. Specifically:
• 5Fn2+4=Ln2+4Ln−4 — wait, the cleaner statement: 5Fn2−4(−1)n=Ln2, where Ln is the n-th Lucas number.
So 5Fn2+4 is a perfect square (equal to Ln2) when n is odd, and 5Fn2−4 is a perfect square when n is even. Together, the two cases cover all Fibonacci numbers.
Example. Is 144 Fibonacci? Compute 5⋅1442=103680. Then 103680+4=103684; 103684≈321.99…, not a perfect square. Try 103680−4=103676; 103676=322, a perfect square. So 144 is Fibonacci. Iterating the recurrence: 1,1,2,3,5,8,13,21,34,55,89,144 — that's F12. So 144=F12.
Non-example. Is 100 Fibonacci? 5⋅1002=50000. Then 50000+4=50004; 50004≈223.61, not a perfect square. 50000−4=49996; 49996≈223.59, not a perfect square either. So 100 is not Fibonacci. The nearest are F11=89 and F12=144.
BigInt arithmetic. For large m, the squares 5m2±4 exceed safe-integer precision. The explorer uses BigInt for these checks, so the test is exact for any input within input-parsing range.
Properties and Identities
Fibonacci numbers satisfy hundreds of identities. A representative selection:
• Cassini's identity: Fn−1Fn+1−Fn2=(−1)n. The product of two terms straddling Fn differs from Fn2 by exactly ±1. • Catalan's identity: Fn2−Fn−rFn+r=(−1)n−rFr2. A generalization of Cassini's. • d'Ocagne's identity: FmFn+1−Fm+1Fn=(−1)nFm−n. • Fast doubling: F2n=Fn(2Fn+1−Fn) and F2n+1=Fn2+Fn+12. These give O(logn) computation by recursion. • Sum identity: F1+F2+⋯+Fn=Fn+2−1. • Sum of squares: F12+F22+⋯+Fn2=FnFn+1. • Sum of odd-indexed: F1+F3+F5+⋯+F2n−1=F2n. • GCD identity: gcd(Fm,Fn)=Fgcd(m,n). A beautiful number-theoretic property — the GCD of Fibonacci numbers is itself a Fibonacci number. • Divisibility: Fm∣Fn if and only if m∣n (for m≥3). Fibonacci-number divisibility mirrors index divisibility. • Zeckendorf's theorem: every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers.
Fibonacci in Nature and Application
Fibonacci numbers appear with striking frequency in biological and physical contexts.
Phyllotaxis. The arrangement of leaves around a stem, seeds in a sunflower, scales on a pinecone, and bracts on a pineapple often follows Fibonacci-based spirals. A sunflower head typically has 34 spirals in one direction and 55 in the other (both Fibonacci numbers). The golden angle ≈137.5°, derived from φ, is the optimal packing angle.
Branching patterns. Some tree species (notably elm and rose) produce branches in counts that grow by Fibonacci numbers.
Pinecone and pineapple spirals. Pinecones have spiral counts in pairs like (5, 8), (8, 13), or (13, 21) — consecutive Fibonacci numbers.
Honeybee genealogy. Male bees (drones) have only one parent; female bees have two. Counting ancestors back, a drone's ancestor counts form the Fibonacci sequence: 1, 1, 2, 3, 5, ...
Cryptography and algorithms. Fibonacci heaps achieve O(1) amortized insertion, and Fibonacci coding is used in some data-compression schemes.
Financial markets. Some traders use Fibonacci retracements (38.2%, 50%, 61.8%) derived from Fibonacci ratios for technical analysis. The mathematical basis is more cultural than rigorous.
Counting compositions.Fn+1 counts the ways to write n as an ordered sum of 1s and 2s — closely related to tiling and combinatorial problems.
Art and architecture. The golden ratio and Fibonacci proportions appear in classical Greek architecture, Renaissance art, and modern design. Some claims are exaggerated; others are well-documented.
Fibonacci and the Golden Ratio
The golden ratio φ=(1+5)/2≈1.618 is the key analytic object behind the Fibonacci sequence.
Limit of ratios. As n→∞:
n→∞limFnFn+1=φ
Even for modest n, the ratio is close to φ: F11/F10=89/55=1.61818….
Why phi.φ is the unique positive number satisfying φ=1+1/φ, equivalently φ2=φ+1. This equation matches the structure of the Fibonacci recurrence. Solving x2−x−1=0 gives φ and ψ=(1−5)/2.
The golden ratio's role in Binet's formula.Fn=(φn−ψn)/5. Since ∣ψ∣<1, the ψn term decays, and Fn≈φn/5 to within 1/2 for all n≥1.
The golden rectangle. A rectangle with side ratio φ:1 has the property that cutting off a square leaves a smaller rectangle with the same side ratio. Drawing diagonals of these nested rectangles approximates the logarithmic spiral, which itself is closely related to natural growth patterns.
Other irrational appearances. The continued-fraction expansion of φ is [1;1,1,1,…] — the simplest possible continued fraction. This makes φ the most irrational number in the sense of being hardest to approximate by rationals.
Common Mistakes
• Index convention confusion. Two common conventions: F0=0,F1=1 (Knuth, OEIS) or F1=F2=1 (this explorer, many classical references). They give the same sequence shifted by one. Always check the convention before quoting a value.
• Floating-point precision errors. Binet's formula or naive double-precision computation breaks at moderate n. F80 already has 17 digits — exceeding double precision. Use BigInt or symbolic computation for exact values.
• Misapplying Gessel's identity. Both 5m2+4 and 5m2−4 must be checked; only one will be a perfect square (or neither, if m is not Fibonacci). Skipping one case incorrectly rejects half of all Fibonacci numbers.
• Naive recursive computation. Computing Fn via the naive recursion fib(n)=fib(n−1)+fib(n−2) has exponential time complexity. Use memoization, iteration, fast doubling, or matrix exponentiation for O(n) or O(logn).
• Confusing Fibonacci with Lucas numbers. Lucas numbers Ln satisfy the same recurrence with L1=1,L2=3. They share many identities with Fibonacci but are a distinct sequence: 1, 3, 4, 7, 11, 18, 29, 47, ...
• Overclaiming nature appearances. Fibonacci spirals appear in many plants but not all. Spurious claims (e.g., "the Mona Lisa uses golden-ratio proportions") are common but often unsupported by careful measurement.
Related Sequences and Concepts
Lucas Numbers — Ln=Ln−1+Ln−2 with L1=1,L2=3. Closely related to Fibonacci; share many identities. Sequence: 1, 3, 4, 7, 11, 18, 29, 47, ...
Golden Ratio — φ=(1+5)/2. The limit of consecutive Fibonacci ratios; appears in Binet's formula.
Tribonacci Numbers — the three-term generalization: Tn=Tn−1+Tn−2+Tn−3. Each term is the sum of the previous three.
Pell Numbers — Pn=2Pn−1+Pn−2 with P0=0,P1=1. Closely related to 2 as Fibonacci is to φ.
Binet's Formula — the closed-form expression for Fn using φ and ψ. The prototype for closed-form solutions of linear recurrences.
Linear Recurrence — the general class. Fibonacci is the simplest non-trivial second-order linear recurrence.
Generating Function — ∑Fnxn=x/(1−x−x2). The rational generating function corresponds to a linear recurrence.
Continued Fractions — convergents of φ are exactly Fn+1/Fn. Connects irrational approximation to Fibonacci.
Zeckendorf Representation — every positive integer has a unique decomposition as a sum of non-consecutive Fibonacci numbers. A base-φ analog of binary representation.
Lucas Sequence — a two-parameter family generalizing Fibonacci. Defined by recurrence Un=PUn−1−QUn−2. Fibonacci is Un(P=1,Q=−1).
Pisano Period — the period of Fibonacci numbers modulo m, denoted π(m). The sequence Fn(modm) is always periodic; the period has interesting number-theoretic properties.
Wythoff Sequences — pairs of sequences whose union is all positive integers, defined using φ. The "lower" Wythoff sequence is ⌊nφ⌋ and the "upper" is ⌊nφ2⌋.
Spiral and Phyllotaxis — the natural appearance of Fibonacci numbers in plant arrangements, sunflower seed spirals, pinecone scales, etc.