Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools


Fibonacci Sequence



Definition
The Golden Ratio
Binet's Formula
Identities and Properties
Lucas Numbers



Each Term from the Two Before It

The Fibonacci sequence is the most famous example of a recursively defined sequence: each term is the sum of the two terms that precede it. From the simplest possible starting values — 11 and 11 — this rule produces a sequence whose growth rate, divisibility structure, and algebraic identities have been studied for centuries. Despite its purely recursive origin, the Fibonacci sequence has an explicit closed-form expression involving the golden ratio.



Definition

The Fibonacci sequence is defined by a two-term recurrence with two initial values:

F1=1,F2=1,Fn=Fn−1+Fn−2(n≥3)F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad (n \geq 3)


The first terms are:

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


Each term after the second is the sum of its two immediate predecessors: 2=1+12 = 1 + 1, 3=1+23 = 1 + 2, 5=2+35 = 2 + 3, 8=3+58 = 3 + 5, and so on. Growth accelerates because each new term absorbs the size of both parents.

An alternative convention starts with F0=0F_0 = 0: the sequence becomes 0,1,1,2,3,5,8,…0, 1, 1, 2, 3, 5, 8, \ldots. The same recurrence applies — only the indexing shifts. Both conventions appear in the literature, and the choice is a matter of context. This page uses F1=1F_1 = 1.

The Fibonacci sequence is neither arithmetic (the differences 0,1,1,2,3,5,…0, 1, 1, 2, 3, 5, \ldots are not constant) nor geometric (the ratios 1,2,1.5,1.6‾,1.6,…1, 2, 1.5, 1.\overline{6}, 1.6, \ldots are not constant either, though they converge).

The Golden Ratio

The ratio of consecutive Fibonacci numbers Fn+1Fn\frac{F_{n+1}}{F_n} settles toward a fixed value as nn grows:

F2F1=1,F3F2=2,F4F3=1.5,F5F4=1.6‾,F6F5=1.6,…\frac{F_2}{F_1} = 1, \quad \frac{F_3}{F_2} = 2, \quad \frac{F_4}{F_3} = 1.5, \quad \frac{F_5}{F_4} = 1.\overline{6}, \quad \frac{F_6}{F_5} = 1.6, \quad \ldots


The limit is the golden ratio:

ϕ=1+52≈1.6180339887…\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\ldots


The number ϕ\phi satisfies the equation ϕ2=ϕ+1\phi^2 = \phi + 1, or equivalently ϕ2−ϕ−1=0\phi^2 - \phi - 1 = 0. This quadratic has a second root ψ=1−52≈−0.618\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618, which also satisfies ψ2=ψ+1\psi^2 = \psi + 1.

The two roots are related: ϕ+ψ=1\phi + \psi = 1 and ϕ⋅ψ=−1\phi \cdot \psi = -1. Since ∣ψ∣<1|\psi| < 1, powers of ψ\psi shrink toward zero, which is why the ratio Fn+1Fn\frac{F_{n+1}}{F_n} converges to ϕ\phi and not to ψ\psi.

Binet's Formula

Despite its recursive definition, the Fibonacci sequence has an explicit closed-form expression:

Fn=ϕn−ψn5F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}


where ϕ=1+52\phi = \frac{1 + \sqrt{5}}{2} and ψ=1−52\psi = \frac{1 - \sqrt{5}}{2}.

The derivation starts by assuming a solution of the form Fn=xnF_n = x^n and substituting into the recurrence Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}. This gives xn=xn−1+xn−2x^n = x^{n-1} + x^{n-2}, which simplifies to the characteristic equation x2=x+1x^2 = x + 1. The two roots are ϕ\phi and ψ\psi. Since the recurrence is linear, any linear combination Fn=Aϕn+BψnF_n = A\phi^n + B\psi^n is also a solution, and the constants AA and BB are determined by the initial conditions F1=1F_1 = 1, F2=1F_2 = 1.

The formula involves irrational numbers — 5\sqrt{5} appears explicitly, and both ϕ\phi and ψ\psi are irrational — yet it always produces an integer. The irrational parts of ϕn\phi^n and ψn\psi^n cancel exactly upon subtraction.

Since ∣ψ∣<1|\psi| < 1, the term ψn\psi^n vanishes for large nn, and Fn≈ϕn5F_n \approx \frac{\phi^n}{\sqrt{5}}. This means the Fibonacci sequence grows exponentially at rate ϕ\phi — roughly 61.8%61.8\% growth per step.

Identities and Properties

The Fibonacci sequence satisfies a network of algebraic identities. Several of the most fundamental are collected here.

Cassini's identity relates three consecutive Fibonacci numbers:

Fn−1Fn+1−Fn2=(−1)nF_{n-1} F_{n+1} - F_n^2 = (-1)^n


The product of the neighbors minus the square of the middle term alternates between +1+1 and −1-1. For n=6n = 6: F5⋅F7−F62=5⋅13−82=65−64=1F_5 \cdot F_7 - F_6^2 = 5 \cdot 13 - 8^2 = 65 - 64 = 1.

Sum of the first $n$ Fibonacci numbers:

∑k=1nFk=Fn+2−1\sum_{k=1}^{n} F_k = F_{n+2} - 1


The running total always lands one short of a Fibonacci number two positions ahead.

Sum of squares:

∑k=1nFk2=Fn⋅Fn+1\sum_{k=1}^{n} F_k^2 = F_n \cdot F_{n+1}


The sum of the first nn squared Fibonacci numbers equals the product of FnF_n and Fn+1F_{n+1}.

Divisibility: gcd⁡(Fm,Fn)=Fgcd⁡(m,n)\gcd(F_m, F_n) = F_{\gcd(m,n)}. The greatest common divisor of two Fibonacci numbers is itself a Fibonacci number, indexed by the GCD of the original indices. This connects the multiplicative structure of the Fibonacci sequence to the GCD of ordinary integers.

Zeckendorf's theorem: every positive integer can be represented as a sum of non-consecutive Fibonacci numbers, and this representation is unique. For example, 30=21+8+1=F8+F6+F130 = 21 + 8 + 1 = F_8 + F_6 + F_1.

Lucas Numbers

The Lucas sequence uses the same recurrence as Fibonacci but starts from different initial values:

L1=1,L2=3,Ln=Ln−1+Ln−2(n≥3)L_1 = 1, \quad L_2 = 3, \quad L_n = L_{n-1} + L_{n-2} \quad (n \geq 3)


The first terms are 1,3,4,7,11,18,29,47,76,123,…1, 3, 4, 7, 11, 18, 29, 47, 76, 123, \ldots. The growth rate is identical to Fibonacci — the ratio of consecutive Lucas numbers also converges to ϕ\phi — but the specific values differ.

The two sequences are tightly linked. The relationship Ln=Fn−1+Fn+1L_n = F_{n-1} + F_{n+1} expresses each Lucas number as the sum of the Fibonacci neighbors flanking it. For n=5n = 5: L5=F4+F6=3+8=11L_5 = F_4 + F_6 = 3 + 8 = 11.

The Binet analogue for Lucas numbers is:

Ln=ϕn+ψnL_n = \phi^n + \psi^n


Where Fibonacci's formula subtracts powers of the two roots and divides by 5\sqrt{5}, Lucas's formula adds them directly. The complementary structure — one sequence from the difference, the other from the sum — is a consequence of both sequences satisfying the same characteristic equation.