Fibonacci Sequence Generator

Historical Origins: Leonardo of Pisa and the Rabbit Problem

The Fibonacci sequence takes its modern name from Leonardo of Pisa (c. 1170 – c. 1250), known posthumously as Fibonacci. In his seminal 1202 treatise Liber Abaci ("The Book of Calculation"), Leonardo introduced the Hindu-Arabic decimal numeral system to Western Europe, replacing the cumbersome Roman numeral system for commerce, trade, and science.

In Chapter 12 of Liber Abaci, Fibonacci posed a recreational mathematics problem regarding the breeding population of a hypothetical colony of rabbits under ideal theoretical conditions:

"A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive?"

Tracking the rabbit pairs month by month yields the sequence:

Remarkably, although named after Fibonacci in Europe following Édouard Lucas's 19th-century scholarship, the sequence had been described centuries earlier in Indian prosody and linguistics by scholars including Acharya Pingala (c. 200 BCE), Virahanka (c. 700 CE), and Hemachandra (c. 1150 CE) in their studies of metrical patterns of short and long syllables in Sanskrit poetry.

Formal Mathematical Definition and Second-Order Recurrence

Mathematically, the Fibonacci sequence is classified as a homogeneous linear second-order recurrence relation with constant coefficients. It is governed by the recurrence formula:

Because it is a second-order relation, two initial boundary conditions are required to uniquely determine the sequence. In contemporary mathematics, these are standardized as:

The recurrence can also be extended backward into negative integers ($n < 0$) by rearranging the formula as $F_{n-2} = F_n - F_{n-1}$, generating the negafibonacci numbers:

Binet's Closed-Form Formula and Analytical Characteristic Derivation

Computing high-index Fibonacci numbers like $F_{100}$ iteratively requires ninety-nine additions. In 1843, French mathematician Jacques Philippe Marie Binet popularized an explicit closed-form function (originally discovered by Leonhard Euler and Daniel Bernoulli in the 18th century):

To derive Binet's formula analytically, assume a solution of exponential form $F_n = r^n$. Substituting into the recurrence relation yields:

This second-degree polynomial is known as the characteristic equation of the Fibonacci recurrence. Solving this quadratic with our Quadratic Formula Calculator gives two roots:

By linear superposition, the general solution is $F_n = C_1 \phi^n + C_2 \psi^n$. Enforcing initial conditions $F_0 = 0$ ($C_1 + C_2 = 0$) and $F_1 = 1$ ($C_1 \phi + C_2 \psi = 1$) uniquely determines $C_1 = 1/\sqrt{5}$ and $C_2 = -1/\sqrt{5}$, yielding Binet's exact formula.

The Golden Ratio Connection and Limit Proof

The deep relationship between Fibonacci numbers and the golden ratio ($\phi$) is one of the most celebrated connections in pure mathematics. If we examine the ratio of consecutive terms:

To prove this convergence analytically using Binet's formula:

Because $|\psi/\phi| = (0.618034 / 1.618034) \approx 0.381966 < 1$, the quotient $(\psi/\phi)^n$ converges to zero exponentially, leaving $\phi$ as the exact asymptotic limit.

The Geometric Golden Spiral and Fibonacci Square Tiling

A striking visual manifestation of Fibonacci numbers is the Fibonacci spiral. When geometric squares whose side lengths are consecutive Fibonacci numbers ($1, 1, 2, 3, 5, 8, 13, \dots$) are tiled adjacently, they construct a sequence of expanding golden rectangles.

Drawing circular quarter-arcs connecting opposing corners within each square generates a continuous smooth spiral curve. As squares are added indefinitely, this piecewise circular construction approximates a true logarithmic spiral governed by the polar equation:

This logarithmic spiral possesses self-similarity: every 90-degree ($\pi/2$ radians) rotation expands the radius by a factor of exactly $\phi \approx 1.618$, maintaining constant geometric proportion across all spatial scales.

Divisibility Properties, GCD Identity, and Fibonacci Primes

In number theory, the Fibonacci sequence exhibits profound arithmetic structural patterns that connect deeply with greatest common divisors and prime factorization:

• Every 3rd Fibonacci Number is Even: Because the sequence starts with an even and two odds ($0, 1, 1$), addition of parity (even + odd = odd; odd + odd = even) ensures that even numbers appear at every index divisible by 3: $F_3 = 2, F_6 = 8, F_9 = 34, F_{12} = 144, \dots$
• Divisibility Sequence Property: If an index $m$ divides an index $n$ ($m \mid n$), then $F_m$ divides $F_n$ ($F_m \mid F_n$). For example, since $4 \mid 12$, $F_4 = 3$ divides $F_{12} = 144$ ($144 / 3 = 48$).
• Strong Divisibility and GCD Identity: The greatest common divisor of any two Fibonacci numbers is itself a Fibonacci number whose index is the GCD of their indices:
  \gcd(F_m, F_n) = F_{\gcd(m, n)}
  For example, $\gcd(F_{12}, F_{18}) = \gcd(144, 2584) = 8 = F_6 = F_{\gcd(12, 18)}$.
• Fibonacci Primes: A Fibonacci number that is also a prime number is called a Fibonacci prime. With the exception of $F_4 = 3$, every Fibonacci prime must have a prime index (such as $F_3=2, F_5=5, F_7=13, F_{11}=89, F_{13}=233$). However, a prime index does not guarantee a prime Fibonacci number (for example, $F_{19} = 4181 = 37 \times 113$). Investigating these factorizations is easily accomplished with our Prime Factorization Calculator.

Pisano Periods and Modular Arithmetic Periodicities

When the Fibonacci sequence is evaluated modulo a positive integer $m$ (taking the remainder of each term divided by $m$), the resulting sequence of remainders repeats in a finite, periodic cycle. This length is known as the Pisano period, denoted $\pi(m)$, named after Leonardo Pisano.

Because there are only $m^2$ possible ordered pairs of remainders $(F_n \bmod m, F_{n+1} \bmod m)$, the pigeonhole principle guarantees that the sequence must repeat within at most $m^2 - 1$ steps. Examples of notable Pisano periods include:

• Modulo 2: $0, 1, 1 \implies \pi(2) = 3$.
• Modulo 3: $0, 1, 1, 2, 0, 2, 2, 1 \implies \pi(3) = 8$.
• Modulo 10: Determines the last decimal digit of every Fibonacci number $\implies \pi(10) = 60$. The last digits repeat cyclically every 60 numbers.
• Modulo 100: Determines the last two decimal digits $\implies \pi(100) = 300$.

Pisano periods are widely used in cryptographic pseudo-random number generation and algorithmic competitive programming to evaluate astronomically large Fibonacci indices like $F_{10^{18}} \bmod 10^9+7$ in logarithmic time.

Zeckendorf's Theorem: Unique Non-Consecutive Base Representation

In 1972, Belgian mathematician Édouard Zeckendorf proved a fundamental positional theorem: every positive integer can be uniquely represented as the sum of one or more distinct, non-consecutive Fibonacci numbers.

The non-consecutive constraint ($c_i c_{i+1} = 0$) prevents ambiguity, because two consecutive terms $F_i + F_{i+1}$ can always be rewritten as their sum $F_{i+2}$. To obtain the Zeckendorf representation of any integer, a simple greedy algorithm suffices: repeatedly subtract the largest Fibonacci number less than or equal to the current remainder.

For example, for $N = 100$: the largest Fibonacci number $\le 100$ is $F_{11} = 89$. The remainder is $100 - 89 = 11$. The largest Fibonacci number $\le 11$ is $F_6 = 8$. The remainder is $11 - 8 = 3 = F_4$. Thus:

This theorem forms the basis of Fibonacci coding in information theory, a universal variable-length prefix code used in data compression that allows self-synchronizing transmission over noisy communication channels.

Real-World Applications in Computer Science, Nature, and Finance

Far from being an abstract curiosity, Fibonacci sequences govern fundamental patterns in physical systems, biology, computational architecture, and economic models:

• Phyllotaxis and Botanical Packing: In botany, the spiral arrangement of leaves around a plant stem, florets on a sunflower head, and scales on pinecones exhibit consecutive Fibonacci numbers (e.g. 34 clockwise spirals and 55 counterclockwise spirals). This geometry maximizes sunlight exposure and minimizes floret crowding around the golden divergence angle of $137.5^\circ$ ($360^\circ \times (1 - 1/\phi)$).
• Fibonacci Search & Fibonacci Heap Data Structures: In computer science, the Fibonacci heap is a priority queue data structure that provides constant amortized time $O(1)$ for insert, decrease-key, and find-minimum operations, critical for accelerating Dijkstra's shortest path and Prim's minimum spanning tree algorithms.
• Financial Technical Analysis: In quantitative trading and technical analysis, traders apply Fibonacci retracement levels (23.6%, 38.2%, 61.8%, 78.6%) derived from Fibonacci ratio relationships to predict support and resistance zones on market pricing charts.

Computational Complexity: Naive Recursion to Matrix Exponentiation

The Fibonacci sequence serves as the quintessential benchmark problem in computer science for demonstrating algorithm efficiency and time-space tradeoffs: