Fibonacci Calculator

What the Fibonacci sequence is

Each term is the sum of the two before it. Start with F(0) = 0 and F(1) = 1, and the rule F(n) = F(n-1) + F(n-2) generates the rest: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. The sequence is entry A000045 in the OEIS, and it is one of the few integer sequences that shows up in number theory, plant biology and algorithm analysis at the same time.

The name comes from Leonardo of Pisa, who published under the name Fibonacci. His 1202 book Liber Abaci introduced the sequence through a rabbit breeding puzzle: start with one pair, each mature pair produces one new pair per month, and young pairs take a month to mature. The count of pairs each month follows the sequence exactly.

Indexing is the first thing to pin down. This page, the OEIS and most programming references start at F(0) = 0. Some textbooks start the list at 1, 1 and call it F(1). The terms themselves are identical; only the labels shift by one, which matters when someone asks for "the 10th term" and two people answer 55 and 89.

Worked example: F(20) and the sum of the first 21 terms

Building the sequence to n = 20 by hand takes 20 additions. The last few steps run: F(16) = 987, F(17) = 1,597, F(18) = 2,584, F(19) = 4,181, and F(20) = 4,181 + 2,584 = 6,765. The next term, F(21), is 6,765 + 4,181 = 10,946.

Adding every term up is easier than it looks, because the running sum is one Fibonacci number away from the next term: F(0) + F(1) + ... + F(n) = F(n+2) - 1. For the 21 terms from F(0) to F(20), the sum is F(22) - 1 = 17,711 - 1 = 17,710. No loop over 21 numbers needed, and the calculator uses the same identity.

Watch how each term is a little over 1.6 times the one before. From F(16) to F(20) the value multiplies by 6,765 / 987 = 6.85, which is 1.618 raised to the 4th power, 6.854. That constant growth rate is the engine behind everything else on this page.

The ratio between neighboring terms closes in on phi

Divide any term by the one before it and the answer walks toward 1.6180339887, the golden ratio phi. Small terms swing around it, then settle:

By the twentieth term the ratio matches phi to eight decimal places. The gap shrinks by a factor of about 2.6 with each step, which is why 6 or 7 terms are enough for a good estimate and 20 are enough for a calculator display.

That link is not a coincidence: phi satisfies x = 1 + 1/x, the same recurrence the ratios obey in the limit. The MathWorld Fibonacci number page works through the algebra, and the golden ratio page on this site approaches the same constant from the geometry side.

Binet's formula, the closed form

You do not need 1,000 additions to reach F(1,000). Binet's formula gives any term directly:

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

where phi = 1.6180339887 and psi = (1 - sqrt(5)) / 2 = -0.6180339887, the two roots of x^2 = x + 1. Try n = 10: phi^10 = 122.99187 and psi^10 = 0.00813, so (122.99187 - 0.00813) / 2.23607 = 55 exactly.

The psi term is always smaller than 0.62 in absolute value, so it fades fast: psi^2 is 0.382, psi^5 is -0.0902, psi^10 is 0.00813. Past n = 10 it cannot move the value by even half a unit, which proves a handy shortcut: F(n) is the nearest whole number to phi^n / sqrt(5) for every n from 0 up.

The same formula explains the ratio convergence. Divide F(n+1) by F(n) in closed form and the psi parts collapse toward zero, leaving phi plus a correction of size 1 / (sqrt(5) x F(n)^2). At n = 20 that correction is about 1 part in 100 million, matching the +0.0000006 percent gap in the table above.

Identities that make checking easy

A handful of identities hold for every n, and they double as checksums when a hand calculation or a spreadsheet goes wrong.

The Cassini row is worth a second look because it says neighboring terms almost square into each other: F(n-1) x F(n+1) misses F(n)^2 by exactly 1, alternating sides. Geometrically, cutting a square of side F(n) off a rectangle of sides F(n) and F(n+1) leaves a rectangle with the same proportions, one step smaller. That is the spiral construction, run on integers.

The gcd identity is the one computer science keeps: it makes Fibonacci numbers a worst case for the Euclidean algorithm, since gcd(F(n+1), F(n)) needs the full n steps.

How fast the numbers grow

Multiplying by about 1.618 per step does not sound fast until you count digits. Each term adds roughly log10(phi) = 0.20899 digits, so F(n) needs about 0.209 x n digits, and the count crosses a new digit roughly every 5 terms.

F(100) already needs 21 digits, past what a 64 bit integer holds. The breaking point for double precision floats comes even earlier: F(78) = 8,944,394,323,791,464 still fits under 2^53 = 9,007,199,254,740,992, but F(79) = 14,472,334,024,676,221 does not. Any spreadsheet or JavaScript program that computes Fibonacci numbers with plain numbers starts rounding from F(79) onward, silently dropping digits.

This calculator stores terms as exact integers, so F(1,000) comes back with all 209 digits instead of a rounded 4.3466557687e208. That is the whole reason a dedicated tool beats a quick spreadsheet formula for large n.

The same growth makes the sequence a number system. Zeckendorf's theorem says every positive integer is a sum of non neighboring Fibonacci numbers in exactly one way: 100 is 89 + 8 + 3, and 1,000 is 987 + 13. Because the largest usable term grows by 1.618 per step, any number needs only about log base phi of itself terms, which is 14 for 1,000 and 29 for a million.

Where the sequence turns up

Plants carry the sequence in their growth patterns. A sunflower head typically packs 34 seed spirals one way and 55 the other; pinecones count 8 and 13 scales; pineapple skins show 8, 13 and 21 rows. The counts are Fibonacci numbers because each new seed or scale emerges at the golden angle, about 137.5 degrees, from the last one, and that spacing packs most efficiently when the visible spiral counts are neighboring Fibonacci numbers.

Counting problems produce the same numbers. The ways to climb a staircase of n steps taking 1 or 2 steps at a time is F(n+1): for n = 4 the count is 5, and F(5) = 5. Tiling a 2 x n strip with dominoes gives F(n+1) as well: 3 ways for a 2 x 3 strip. Every arrangement ends in either a vertical domino or two horizontal ones, which is the recurrence in disguise.

In computing, Fibonacci numbers set the growth of Fibonacci heaps, drive the probe sequence of Fibonacci hashing, and mark the worst case input for the Euclidean algorithm. The last digits of the sequence repeat with period 60, a Pisano period, which is why F(60) ends in 0 and F(61) in 1, exactly like F(0) and F(1).

The sequence even has a negative branch. Extending the recurrence backward gives F(-1) = 1, F(-2) = -1, F(-3) = 2, F(-4) = -3, and in general F(-n) = (-1)^(n+1) x F(n). The values mirror the positive ones, sign flipped by parity.

Indexing traps and common mistakes

Three mistakes account for nearly every wrong Fibonacci answer:

• Off by one on the start. Lists that begin 1, 1, 2 versus 0, 1, 1, 2 shift every label. State whether your F(1) is 1 or 0 before comparing results with anyone.
• Float rounding past F(79). A calculator or spreadsheet using ordinary floating point numbers returns 14,472,334,024,676,220 for F(79), one less than the true 14,472,334,024,676,221, and the error compounds from there.
• Recursion without a table. The naive recursive definition makes millions of calls for n around 40, because it recomputes the same terms over and over. The work is linear if each term is computed once and kept.

A quick self check catches most errors: F(10) must be 55, the sum through F(10) must be 143, and the last digit pattern must restart every 60 terms. If any of those fail, the indexing is off before the arithmetic even starts.