What is the formula for the n-th Fibonacci number?

The recursive definition is F sub n equals F sub n minus 1 plus F sub n minus 2. Binet's closed-form formula gives F sub n equals phi to the n power minus psi to the n power, divided by the square root of 5, where phi is the golden ratio (1 plus root 5) over 2 and psi is (1 minus root 5) over 2. This explorer computes Fibonacci with arbitrary-precision integers for exact results at any index.

How do you test whether a number is in the Fibonacci sequence?

A positive integer m is a Fibonacci number if and only if 5 times m squared plus 4 or 5 times m squared minus 4 is a perfect square. This is Gessel's identity from 1972. Once confirmed, the index is found by iterating the Fibonacci recurrence until the term equals m.

What is the golden ratio and how does it relate to Fibonacci?

The golden ratio phi equals (1 plus square root of 5) divided by 2, approximately 1.618. As n grows, the ratio of consecutive Fibonacci numbers F sub n plus 1 divided by F sub n approaches phi. Phi is the positive root of the characteristic equation x squared equals x plus 1, which is the equation underlying the Fibonacci recurrence.

Where does the Fibonacci sequence appear in mathematics and nature?

Fibonacci numbers appear in number theory (Zeckendorf's theorem, Lucas sequences), in combinatorics (tilings, paths in graphs, compositions of integers), in computer science (recursive algorithms, Fibonacci heaps), and in nature (spiral patterns in plants, the arrangement of petals, leaves, and seeds). The golden ratio appears in art, architecture, and design.

Fibonacci Sequence Calculator — Exact Arbitrary-Precision Terms

Q: What is the Fibonacci sequence?

The Fibonacci sequence is an integer sequence where each term equals the sum of the two preceding ones, starting from 1 and 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. The recurrence is F sub n equals F sub n minus 1 plus F sub n minus 2, with initial values F sub 1 equals F sub 2 equals 1.

Listing the First N Terms

DemoTen terms, thirty terms, the cap, one term

Step 0 of 4

The explorer opens on the List first N tab, one of four tabs across the top of the card; the small ? beside each tab shows what the mode does. Type how many terms you want in the Show first box and click Update or press Enter. Three cards answer at once: Showing gives the count, Largest the last term with its index, and Sum the total of the listed terms, which for Fibonacci numbers is

F_{N+2} - 1

. Under the cards every term is laid out as a tile with its index above its value, so

F_1 = 1

to

F_N

can be read in order.

The box accepts

1

to

100

:

10

gives

F_{10} = 55

with the sum

143

,

30

gives

F_{30} = 832,040

with the sum

2,178,308

, and

200

is capped at

100

terms, ending at

F_{100} = 354,224,848,179,261,915,075

with the sum

927,372,692,193,078,999,175

; a single term gives

F_1 = 1

. Large values are printed with thousands separators. A count of 0, a decimal or an empty box is refused with "Enter a positive integer." There is no Reset button: type a new count and click Update again. The panel on the right, List first N, states the rule the tiles come from, and its walkthrough repeats the last term and the sum with your own

N

. What the terms are is explained in what is the fibonacci sequence.

Listing a Range of Indexes

DemoThe range tab, a new range, two bad ranges

Step 0 of 4

Click the List a – b tab to list the terms between two positions instead of starting from

1

. Type the From index and the To index and click List range or press Enter. The cards give the Count

b - a + 1

, the Smallest term

F_a

and the Largest term

F_b

, and the tiles below list every term in between with its index. The tab opens with

5

to

15

, 11 terms from

F_{5} = 5

to

F_{15} = 610

; indexes

10

to

20

give 11 terms from

55

to

6,765

.

Both boxes must hold positive integers, the first no larger than the second, and the range may hold at most

100

terms; otherwise a red box explains: "Enter two positive integer indexes", "From-index must be less than or equal to to-index", or "Range too wide — cap is 100 terms". The panel on the right, List a – b, explains the mode, and its walkthrough names the smallest and largest term of your range. The rule each tile uses is explained in the recurrence and binet's formula.

Testing a Number

DemoThe test tab, a non-member, a member, 0

Step 0 of 4

Click the Test a number tab to ask whether a given positive integer is a Fibonacci number. Type it in the Test number box and click Check or press Enter. A green box with a tick answers yes and names the index, as for the opening value

144

, which is

F_{12}

; a red box with a cross answers no, as for

100

, and the walkthrough on the right then shows the two nearest Fibonacci numbers,

F_{11} = 89

and

F_{12} = 144

. A large value is handled the same way:

6,765

is

F_{20}

.

The box takes positive integers only;

0

, a negative number or a decimal is refused with "Enter a positive integer". The test behind the answer is exact: the explorer uses the identity that

m

is a Fibonacci number exactly when

5m^2 + 4

or

5m^2 - 4

is a perfect square; if it is, the index is found, otherwise the two nearest Fibonacci numbers are shown, so no list has to be searched. The panel on the right, Test a number, states this rule, and its walkthrough carries out the arithmetic for your number. The rule itself is explained in the membership test — gessel's identity.

Looking Up a Term by Index

DemoThe lookup tab, two indexes, n = 0

Step 0 of 4

Click the Lookup by index tab to compute one term directly. Type the position in the Index n box and click Get term or press Enter. Two cards answer: Index repeats

n

and Value gives

F_n

with its index as a subscript. The tab opens with

n = 50

, which gives

F_{50} = 12,586,269,025

;

n = 60

gives

1,548,008,755,920

and

n = 90

gives

2,880,067,194,370,816,120

. The box takes positive integers only;

0

is refused with "Enter a positive integer index".

The panel on the right has two parts in every mode. How it works names the rule the mode uses, here

F_n = F_{n-1} + F_{n-2}

with

F_1 = F_2 = 1

, and links to the section of this page that explains it; Walkthrough applies the rule to the numbers you typed, so for the lookup it shows the arithmetic with your

n

filled in. Both change as soon as you switch tabs or click a button. The rule and where it comes from are in the recurrence and binet's formula.

What is the Fibonacci Sequence?

The Fibonacci sequence is defined by the linear recurrence

F_n = F_{n-1} + F_{n-2}

with initial conditions

F_1 = F_2 = 1

. The first terms are:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, \ldots

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

F_1 = F_2 = 1

. Other conventions start at

F_0 = 0, F_1 = 1

(giving the same sequence shifted by one). Be careful when comparing references.

Exact computation. Fibonacci numbers grow exponentially —

F_{100}

has 21 digits,

F_{1000}

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 definition is given in definition and the sequence is placed among the others in Fibonacci numbers.

The closed form is derived in Binet.

The identities the test rests on are collected in identities and properties.

More identities, with proofs, are in identities and properties; the companion sequence is Lucas numbers.

The sequence is summarised in Fibonacci at a glance.

The Recurrence and Binet's Formula

The recurrence.

F_n = F_{n-1} + F_{n-2}

is a second-order linear recurrence with constant coefficients. Its characteristic equation is

x^2 = x + 1

with roots

\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803398\ldots, \quad \psi = \frac{1 - \sqrt{5}}{2} \approx -0.61803398\ldots

\varphi

is the golden ratio.

Binet's formula. The closed-form expression for

F_n

is

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

Since

|\psi| < 1

,

\psi^n

shrinks rapidly to zero, and

F_n

is well-approximated by

\varphi^n / \sqrt{5}

for large

n

.

Why the formula gives an integer.

\varphi

and

\psi

are irrational, but the combination

\varphi^n - \psi^n

always lies in

\sqrt{5} \mathbb{Z}

— the difference of conjugate irrational powers cancels into a rational multiple of

\sqrt{5}

. Dividing by

\sqrt{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.

\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}

. Matrix exponentiation by repeated squaring computes

F_n

in

O(\log n)

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

5 m^2 + 4 \quad \text{or} \quad 5 m^2 - 4

is a perfect square. Once one of these is a perfect square, the index

n

is found by iterating the Fibonacci recurrence until

F_n = 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:

•

5 F_n^2 + 4 = L_n^2 + 4 L_n - 4

— wait, the cleaner statement:

5 F_n^2 - 4 (-1)^n = L_n^2

, where

L_n

is the

n

-th Lucas number.

So

5 F_n^2 + 4

is a perfect square (equal to

L_n^2

) when

n

is odd, and

5 F_n^2 - 4

is a perfect square when

n

is even. Together, the two cases cover all Fibonacci numbers.

Example. Is 144 Fibonacci? Compute

5 \cdot 144^2 = 103680

. Then

103680 + 4 = 103684

;

\sqrt{103684} \approx 321.99\ldots

, not a perfect square. Try

103680 - 4 = 103676

;

\sqrt{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

F_{12}

. So

144 = F_{12}

.

Non-example. Is 100 Fibonacci?

5 \cdot 100^2 = 50000

. Then

50000 + 4 = 50004

;

\sqrt{50004} \approx 223.61

, not a perfect square.

50000 - 4 = 49996

;

\sqrt{49996} \approx 223.59

, not a perfect square either. So 100 is not Fibonacci. The nearest are

F_{11} = 89

and

F_{12} = 144

.

BigInt arithmetic. For large

m

, the squares

5 m^2 \pm 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:

F_{n-1} F_{n+1} - F_n^2 = (-1)^n

. The product of two terms straddling

F_n

differs from

F_n^2

by exactly

\pm 1

.
• Catalan's identity:

F_n^2 - F_{n-r} F_{n+r} = (-1)^{n-r} F_r^2

. A generalization of Cassini's.
• d'Ocagne's identity:

F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}

.
• Fast doubling:

F_{2n} = F_n (2 F_{n+1} - F_n)

and

F_{2n+1} = F_n^2 + F_{n+1}^2

. These give

O(\log n)

computation by recursion.
• Sum identity:

F_1 + F_2 + \cdots + F_n = F_{n+2} - 1

.
• Sum of squares:

F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1}

.
• Sum of odd-indexed:

F_1 + F_3 + F_5 + \cdots + F_{2n-1} = F_{2n}

.
• GCD identity:

\gcd(F_m, F_n) = F_{\gcd(m, n)}

. A beautiful number-theoretic property — the GCD of Fibonacci numbers is itself a Fibonacci number.
• Divisibility:

F_m \mid F_n

if and only if

m \mid n

(for

m \geq 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

\approx 137.5°

, derived from

\varphi

, 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.

F_{n+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

\varphi = (1 + \sqrt{5})/2 \approx 1.618

is the key analytic object behind the Fibonacci sequence.

Limit of ratios. As

n \to \infty

:

\lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \varphi

Even for modest

n

, the ratio is close to

\varphi

:

F_{11}/F_{10} = 89/55 = 1.61818\ldots

.

Why phi.

\varphi

is the unique positive number satisfying

\varphi = 1 + 1/\varphi

, equivalently

\varphi^2 = \varphi + 1

. This equation matches the structure of the Fibonacci recurrence. Solving

x^2 - x - 1 = 0

gives

\varphi

and

\psi = (1 - \sqrt{5})/2

.

The golden ratio's role in Binet's formula.

F_n = (\varphi^n - \psi^n)/\sqrt{5}

. Since

|\psi| < 1

, the

\psi^n

term decays, and

F_n \approx \varphi^n / \sqrt{5}

to within

1/2

for all

n \geq 1

.

The golden rectangle. A rectangle with side ratio

\varphi : 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

\varphi

is

[1; 1, 1, 1, \ldots]

— the simplest possible continued fraction. This makes

\varphi

the most irrational number in the sense of being hardest to approximate by rationals.

The ratio is the subject of the golden ratio.

Common Mistakes

• Index convention confusion. Two common conventions:

F_0 = 0, F_1 = 1

(Knuth, OEIS) or

F_1 = F_2 = 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

.

F_{80}

already has 17 digits — exceeding double precision. Use BigInt or symbolic computation for exact values.

• Misapplying Gessel's identity. Both

5m^2 + 4

and

5m^2 - 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

F_n

via the naive recursion

\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

has exponential time complexity. Use memoization, iteration, fast doubling, or matrix exponentiation for

O(n)

or

O(\log n)

.

• Confusing Fibonacci with Lucas numbers. Lucas numbers

L_n

satisfy the same recurrence with

L_1 = 1, L_2 = 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.

Index conventions and recursive definitions are explained in definition and notation and explicit and recursive definitions.

Related Sequences and Concepts

Lucas Numbers —

L_n = L_{n-1} + L_{n-2}

with

L_1 = 1, L_2 = 3

. Closely related to Fibonacci; share many identities. Sequence: 1, 3, 4, 7, 11, 18, 29, 47, ...

Golden Ratio —

\varphi = (1 + \sqrt{5})/2

. The limit of consecutive Fibonacci ratios; appears in Binet's formula.

Tribonacci Numbers — the three-term generalization:

T_n = T_{n-1} + T_{n-2} + T_{n-3}

. Each term is the sum of the previous three.

Pell Numbers —

P_n = 2 P_{n-1} + P_{n-2}

with

P_0 = 0, P_1 = 1

. Closely related to

\sqrt{2}

as Fibonacci is to

\varphi

.

Binet's Formula — the closed-form expression for

F_n

using

\varphi

and

\psi

. 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 —

\sum F_n x^n = x/(1 - x - x^2)

. The rational generating function corresponds to a linear recurrence.

Continued Fractions — convergents of

\varphi

are exactly

F_{n+1}/F_n

. Connects irrational approximation to Fibonacci.

Zeckendorf Representation — every positive integer has a unique decomposition as a sum of non-consecutive Fibonacci numbers. A base-

\varphi

analog of binary representation.

Lucas Sequence — a two-parameter family generalizing Fibonacci. Defined by recurrence

U_n = P U_{n-1} - Q U_{n-2}

. Fibonacci is

U_n(P = 1, Q = -1)

.

Pisano Period — the period of Fibonacci numbers modulo

m

, denoted

\pi(m)

. The sequence

F_n \pmod m

is always periodic; the period has interesting number-theoretic properties.

Wythoff Sequences — pairs of sequences whose union is all positive integers, defined using

\varphi

. The "lower" Wythoff sequence is

\lfloor n \varphi \rfloor

and the "upper" is

\lfloor n \varphi^2 \rfloor

.

Spiral and Phyllotaxis — the natural appearance of Fibonacci numbers in plant arrangements, sunflower seed spirals, pinecone scales, etc.

The neighbouring calculators are the geometric sequence calculator, the prime numbers calculator and the triangular numbers calculator; the lessons are Lucas numbers and geometric sequences.