Fibonacci calculator
The n-th term, the sum and the list — or test a number. Exact, however large.
What is the Fibonacci sequence?
It starts with F(0) = 0 and F(1) = 1, and every later term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 … (OEIS A000045). So F(10) = 55, F(20) = 6,765 and F(100) = 354,224,848,179,261,915,075. This calculator adds exact whole numbers, so large terms have every digit right.
What is the sum of the first n Fibonacci numbers?
F(0) + F(1) + … + F(n) = F(n + 2) − 1. For n = 10: 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 = F(12) − 1 = 144 − 1.
How do I check whether a number is a Fibonacci number?
A positive integer N is a Fibonacci number exactly when 5N² + 4 or 5N² − 4 is a perfect square (OEIS A000045). For 144: 5 × 144² + 4 = 103,684 = 322², so 144 is F(12). For 145, neither 5N² + 4 nor 5N² − 4 is a square, so it is not one. The calculator also tells you where a non-Fibonacci number falls between two terms.
What are Lucas numbers, and what if I start from other numbers?
Lucas numbers use the same rule with different starting values, L(0) = 2 and L(1) = 1: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 … (OEIS A000032); L(n) = F(n − 1) + F(n + 1). Choose “Custom start” to try any two whole numbers: every such sequence is G(n) = G(0) × F(n − 1) + G(1) × F(n), with F(−1) = 1, and its terms add up the same way: G(0) + … + G(n) = G(n + 2) − G(1).
How is the Fibonacci sequence related to the golden ratio?
The ratio of a term to the one before it approaches the golden ratio φ = (1 + √5) ÷ 2 = 1.6180339887…: 89 ÷ 55 = 1.6182, 144 ÷ 89 = 1.6180. Lucas numbers behave the same way: 123 ÷ 76 = 1.6184. The table shows each ratio. To split a length in the golden ratio, use the golden ratio calculator.
Worked example: how big do the terms get?
F(30) = 832,040, and F(1000) already has 209 digits, beginning 4346655768. The number of digits grows almost steadily: each new term multiplies the previous one by about φ, so it adds log₁₀ φ = 0.20899 digits, or roughly one new digit every five terms. That is why F(n) has about 0.209 × n digits and why the calculator uses exact integer arithmetic rather than ordinary decimals, which keep only about 15 to 16 significant digits.
Why not use Binet's formula?
Binet's closed form says F(n) is the nearest integer to φⁿ ÷ √5, which is exact in mathematics. In double-precision arithmetic, however, the rounding error grows with n: computed this way, the first wrong answer appears at n = 71. The recurrence, done with integers, never loses a digit, so the calculator relies on it, with a fast doubling method for large n.
Which Fibonacci numbers are even?
Every third one: the terms at positions 3 (2), 6 (8), 9 (34), 12 (144), 15 (610) are even, and the two between them are odd. This follows from the recurrence, since odd + odd = even and odd + even = odd, so the parity pattern repeats as odd, odd, even. The same kind of repeating pattern appears modulo any whole number, though its length changes.
Common mistakes with Fibonacci numbers
Counting from a different start. This calculator uses F(0) = 0 and F(1) = 1, so the tenth term in a list that begins at F(1) is F(10) = 55, while some textbooks begin 1, 1, 2 with F(1) = 1 and F(2) = 1 and others with 0 as the first term; check which one you mean before comparing answers. Mixing up Fibonacci and Lucas numbers, which share the rule but start with 2 and 1. Using a rounded golden-ratio formula for large terms, as above. Forgetting that the sum of the first terms is F(n + 2) − 1, not F(n + 1).
Where do the formulas come from?
From OEIS entries A000045 (Fibonacci numbers: the recurrence, the 5N² ± 4 test, the sum F(n + 2) − 1) and A000032 (Lucas numbers). Donald Knuth, The Art of Computer Programming, volume 1, section 1.2.8 “Fibonacci numbers” is the classic treatment. Terms are checked against the OEIS tables of F(n) and L(n) in this calculator’s automated tests.
Sources: OEIS A000045 and A000032; D. E. Knuth, The Art of Computer Programming, vol. 1, section 1.2.8. Related: the golden ratio calculator and the sequence calculator for arithmetic and geometric sequences.