Fibonacci Generator

About Fibonacci Generator

How the Sequence Is Built

The rule is simple. Define F(0) = 0, F(1) = 1, then for every n after that: F(n) = F(n-1) + F(n-2). That single recurrence produces a sequence that appears across mathematics, nature, and computer science. The first 20 terms:

n	F(n)	F(n)/F(n-1)
0	0	-
1	1	-
2	1	1.000000
3	2	2.000000
4	3	1.500000
5	5	1.666667
6	8	1.600000
7	13	1.625000
8	21	1.615385
9	34	1.619048
10	55	1.618182
11	89	1.617978
12	144	1.618056
13	233	1.618026
14	377	1.618037
15	610	1.618033
16	987	1.618034
17	1597	1.618034
18	2584	1.618034
19	4181	1.618034
20	6765	1.618034

Notice how the ratio column settles toward 1.618034 - that is the golden ratio, phi.

How Does the Ratio Converge to Phi?

The golden ratio phi = (1 + sqrt(5)) / 2, roughly 1.6180339887. As n grows, the ratio F(n)/F(n-1) approaches phi with increasing accuracy. By n = 15, the ratio is already correct to six decimal places. This convergence is not a coincidence - phi is the positive root of the equation x^2 = x + 1, and the Fibonacci recurrence satisfies exactly that relationship.

The connection runs even deeper. Binet's formula gives a closed-form expression for any Fibonacci number without computing all the previous terms:

F(n) = (phi^n - psi^n) / sqrt(5)

where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. Since |psi| is less than 1, psi^n shrinks toward zero, so for large n, F(n) is approximately phi^n / sqrt(5), rounded to the nearest integer. The Golden Ratio Calculator lets you explore phi-based proportions for design work.

Which Fibonacci Numbers Are Prime?

A Fibonacci prime is a Fibonacci number that is also a prime number. The first several are 2, 3, 5, 13, 89, 233, and 1597. A useful property: if F(n) is prime (with the exception of F(4) = 3), then n itself must be prime. But the reverse is not always true - F(19) = 4181 = 37 x 113, and 19 is prime. This gives a quick filter: if n is composite and n > 4, F(n) cannot be prime. Use the Prime Factorization tool to break down individual Fibonacci numbers.

n	F(n)	Prime?
3	2	Yes
4	3	Yes
5	5	Yes
7	13	Yes
11	89	Yes
13	233	Yes
17	1597	Yes
23	28657	Yes
29	514229	Yes
43	433494437	Yes

Fibonacci Identities and Properties

The sequence is packed with identities that make it a favourite topic in number theory and competition mathematics.

Identity	Formula	Example
Sum of first n terms	F(1) + F(2) + ... + F(n) = F(n+2) - 1	1+1+2+3+5+8 = 21-1 = 20
Sum of squares	F(1)^2 + ... + F(n)^2 = F(n) x F(n+1)	1+1+4+9+25 = 5 x 8 = 40
Cassini's identity	F(n-1) x F(n+1) - F(n)^2 = (-1)^n	5 x 13 - 8^2 = 65 - 64 = 1
GCD property	gcd(F(m), F(n)) = F(gcd(m,n))	gcd(F(6), F(9)) = gcd(8,34) = 2 = F(3)
Divisibility	F(m) divides F(n) if m divides n	F(3)=2 divides F(12)=144
Last digits cycle	Pisano period for mod 10 = 60	Last digits repeat every 60 terms

The Pisano period result means the final digit of every Fibonacci number repeats in a cycle of length 60. So F(1) and F(61) both end in 1, F(2) and F(62) both end in 1, and so on. Pisano periods exist for every modulus, and they are important in modular arithmetic. The Modulo Calculator can help explore these cycles.

Fibonacci in Nature and Design

Fibonacci numbers appear in the arrangement of leaves, seeds, and petals across many plant species. The pattern is connected to efficient packing and growth.

Where It Appears	What to Count	Typical Fibonacci Number
Sunflower seed spirals	Clockwise and anticlockwise spiral counts	34 and 55 (or 55 and 89)
Pinecone spirals	Spiral arms in each direction	8 and 13
Pineapple scales	Hexagonal spiral rows	8, 13, 21
Flower petals	Number of petals	Lilies 3, buttercups 5, daisies 13/21/34
Tree branching	Branch points per level	1, 2, 3, 5, 8...
Nautilus shell chambers	Growth ratio between chambers	Approaches phi

The reason Fibonacci numbers appear so often in plant growth is connected to the angle of divergence between successive leaves or seeds. The most irrational number (the one hardest to approximate with fractions) is the golden ratio, and its associated angle - about 137.5 degrees - gives the most even distribution of seeds around a centre.

The Golden Spiral

Toggle the spiral view in this tool to see how Fibonacci numbers form a tiling of squares. Start with a 1x1 square, place another 1x1 next to it, then a 2x2 square along the longer side, then a 3x3, a 5x5, and so on. The resulting rectangle approaches the golden rectangle, and a quarter-circle arc drawn through each square traces the Fibonacci spiral - an approximation of the logarithmic golden spiral.

True golden spirals (based on the continuous function r = phi^(2theta/pi)) appear in galaxy arms, hurricane structure, and shell growth. The Fibonacci tiling version is a discrete approximation that matches the continuous spiral closely.

Fibonacci in Computer Science

The sequence is a standard example in algorithm courses for comparing recursive and iterative approaches.

Algorithm	Time Complexity	Space	Notes
Naive recursion	O(2^n)	O(n) stack	Exponential - recomputes subproblems
Memoised recursion	O(n)	O(n)	Stores computed values
Iterative (bottom-up)	O(n)	O(1)	Only tracks two previous values
Matrix exponentiation	O(log n)	O(1)	Uses [[1,1],[1,0]]^n
Binet's formula	O(1)	O(1)	Floating-point errors for large n

The naive recursive approach is the classic example of why memoisation or dynamic programming matters - computing F(50) recursively without caching would take over 10^10 operations.

Fibonacci in Financial Markets

Fibonacci retracements are a popular technical analysis tool in trading. After a price move, traders look for pullbacks to levels at 23.6%, 38.2%, 50%, 61.8%, and 78.6% of the move. The 61.8% level comes from the inverse of phi (1/1.618 = 0.618), and 38.2% is 1 - 0.618. These are not predictive in a scientific sense, but they are widely used as support and resistance levels because many traders watch them, creating a degree of self-fulfilling behaviour.

Generalisations of Fibonacci

Sequence	Rule	First Terms
Lucas numbers	Same rule, start 2, 1	2, 1, 3, 4, 7, 11, 18, 29
Tribonacci	Sum of previous three	0, 0, 1, 1, 2, 4, 7, 13, 24
Tetranacci	Sum of previous four	0, 0, 0, 1, 1, 2, 4, 8, 15
Pell numbers	P(n) = 2P(n-1) + P(n-2)	0, 1, 2, 5, 12, 29, 70
Negative Fibonacci	Extend left: F(-n) = (-1)^(n+1) F(n)	..., 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5...

Lucas numbers share the same recurrence as Fibonacci but start with 2 and 1. They converge to the same golden ratio and satisfy the identity L(n) = F(n-1) + F(n+1). The tribonacci constant (the ratio tribonacci numbers converge to) is approximately 1.83929.

For exploring the golden ratio directly in design contexts, the Golden Ratio Calculator computes matching proportions from any input dimension. To study binomial coefficients and their connection to Fibonacci diagonals, see Pascal's Triangle.

Common Mistakes and Edge Cases

The most common source of confusion is the starting index. Some sources begin with F(0) = 0, F(1) = 1 (the modern convention used here and by the On-Line Encyclopedia of Integer Sequences entry A000045), while older texts start at F(1) = 1, F(2) = 1. That single shift causes every identity that depends on n to look different in the literature, so always check which indexing convention a proof uses before applying an identity.

Another pitfall is using Binet's formula for large n without arbitrary-precision arithmetic. JavaScript's double-precision floats lose integer accuracy above roughly F(78) = 8,944,394,323,791,464, because 2^53 is about 9.007 x 10^15. For exact values beyond that, an iterative BigInt loop is the only reliable approach. The naive recursive version fib(n) = fib(n-1) + fib(n-2) is famously bad: computing fib(40) triggers over 200 million recursive calls because every sub-result is recomputed. Memoisation or an iterative loop reduces this to 40 additions.

A subtle point on Fibonacci primes: it is conjectured but not proven that infinitely many exist. Only 35 Fibonacci primes were known as of 2024, with the largest confirmed one being F(104911), a 21,925-digit number found in 2015.

Historical Context

The sequence is named after Leonardo of Pisa (c. 1170-1250), known as Fibonacci, who presented it in his 1202 book Liber Abaci as a model of rabbit population growth. Starting with one breeding pair, and assuming no deaths and a one-month maturation period, Fibonacci showed that the population at month n equals F(n). The problem was not original to him - Indian mathematicians including Pingala (c. 200 BCE), Virahanka (c. 700 CE), and Hemachandra (c. 1150) had studied the same recurrence in the context of Sanskrit poetic metre, roughly 50 years before Liber Abaci appeared in Europe.

The term "Fibonacci sequence" itself was not coined until Edouard Lucas used it in the 1870s. Lucas also introduced the related sequence (2, 1, 3, 4, 7, 11...) that now bears his name. The golden ratio connection was known much earlier - Euclid described the "extreme and mean ratio" in his Elements around 300 BCE - but it was Kepler who first noted in 1611 that the ratio of consecutive Fibonacci numbers converges to phi.

Sources

• OEIS A000045 - Fibonacci Numbers
• Wolfram MathWorld - Fibonacci Number
• Wolfram MathWorld - Binet's Formula
• OEIS A005478 - Fibonacci Primes
• Plus Magazine (University of Cambridge) - Fibonacci Sequence Introduction
• Encyclopedia Britannica - Fibonacci (Leonardo of Pisa)

All computation runs in your browser. No data is sent to any server.