Fibonacci Number Calculator

How it works

The Fibonacci sequence starts 0, 1 and then every term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Written F(n), the rule is F(n) = F(n − 1) + F(n − 2) with F(0) = 0 and F(1) = 1. It is sequence A000045 in the OEIS and turns up in counting problems, in the arrangement of leaves and seeds, and in the running time of Euclid's algorithm.

The terms grow quickly: F(10) is 55, F(50) is over twelve billion, F(100) has 21 digits and F(1000) has 209. Spreadsheets and most calculators keep only about 16 significant digits, so they are exact up to F(78) = 8,944,394,323,791,464 and approximate beyond. This calculator adds the terms as exact integers, so every digit shown is correct all the way to F(1000).

Divide any term by the one before it and the ratio settles towards the golden ratio φ = (1 + √5) ÷ 2 ≈ 1.6180339887, alternating above and below it. Binet's formula F(n) = (φⁿ − ψⁿ) ÷ √5, with ψ = (1 − √5) ÷ 2 ≈ −0.618, explains why: the ψⁿ part shrinks towards zero, so F(n) is the nearest whole number to φⁿ ÷ √5 and the ratio of consecutive terms misses φ by exactly ψⁿ⁻¹ ÷ F(n − 1).

Formula

F(0) = 0,  F(1) = 1,  F(n) = F(n − 1) + F(n − 2)
φ = (1 + √5) ÷ 2 ≈ 1.6180339887,  ψ = (1 − √5) ÷ 2 = −1 ÷ φ
Binet:  F(n) = (φⁿ − ψⁿ) ÷ √5
F(n) ÷ F(n − 1) − φ = ψⁿ⁻¹ ÷ F(n − 1)

Example

n = 10: the sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, so F(10) = 55, a 2-digit number between F(9) = 34 and F(11) = 89. The ratio 55 ÷ 34 = 1.6176470588 is below φ = 1.6180339887 by 3.869 × 10⁻⁴.

F(50) = 12,586,269,025 (11 digits) and F(100) = 354,224,848,179,261,915,075 (21 digits), both exact. At n = 100 the ratio matches φ to about 41 decimal places.

Assumptions and limitations

• n is a whole number from 0 to 1,000. Negative indices (the negafibonacci numbers) are not covered; F(n − 1) is shown as a dash at n = 0.
• F(n), F(n − 1) and F(n + 1) are exact integers. The ratio F(n) ÷ F(n − 1) is computed in double precision and shown to 10 decimal places; it is undefined at n = 0 and n = 1 and shown as a dash there.
• The gap between the ratio and φ is computed from the identity ψⁿ⁻¹ ÷ F(n − 1) in logarithms, so it is shown even when it is far below double precision (about 10⁻⁴¹⁸ at n = 1,000).
• The table lists F(0) up to F(25) at most.

Frequently asked questions