Binet's Formula: Computing Fibonacci Numbers Without Recursion

The defining rule of the Fibonacci sequence, F(n) = F(n−1) + F(n−2), only tells you how to get the next term from the two before it. To find F(50) that way, you have to compute every term from F(2) onward first. Binet's formula solves a different problem entirely: it gives you a single expression that computes F(n) directly from n, with no earlier terms involved at all.

The formula itself

Binet's formula states: F(n) = (φⁿ − ψⁿ) / √5, where φ = (1 + √5) / 2 ≈ 1.6180339887 is the golden ratio, and ψ = (1 − √5) / 2 ≈ −0.6180339887 is its algebraic conjugate (note that ψ = −1/φ, and ψ is also sometimes written as 1 − φ). Plug in n and, after the dust settles, you get back a whole number — despite every ingredient in the formula being irrational.

Why the irrational parts vanish

That last part is the genuinely surprising piece: φⁿ and ψⁿ are each irrational numbers for essentially any n, yet their difference, divided by √5, always comes out to a plain integer. The reason is that both φ and ψ are roots of the same quadratic equation, x² = x + 1, which means any sequence built from a combination of φⁿ and ψⁿ automatically satisfies the Fibonacci recurrence itself. Binet's formula is the specific combination of the two roots that matches the sequence's actual starting values, F(0)=0 and F(1)=1. Because both root-sequences individually obey the Fibonacci addition rule, and the formula is just a fixed linear combination of the two, the whole expression obeys it too — and once you know the first two outputs are exact integers (0 and 1), every subsequent output produced by the same recurrence has to be an integer as well, algebraically guaranteed rather than a coincidence of rounding.

A name that undersells its history

The formula is named after Jacques Philippe Marie Binet, a 19th-century French mathematician who published a proof of it in 1843 — but, in a detail that's common enough in the history of mathematics to have its own name (Stigler's law of eponymy), Binet wasn't actually the first to discover it. The same formula appears in the work of Abraham de Moivre more than a century earlier, in the 1730s, in the context of solving linear recurrence relations generally, and it's also been attributed to Leonhard Euler and Daniel Bernoulli in various forms around the same period. It's Binet's name that stuck for the Fibonacci-specific version, but the underlying technique — solving a linear recurrence by finding the roots of its associated quadratic and combining them — predates him and generalizes well beyond just this one sequence.

Where the practical limit comes from

Computed with ordinary floating-point arithmetic, Binet's formula stops being exactly reliable once n gets large enough that rounding error in computing φⁿ and ψⁿ exceeds half an integer — in practice, somewhere in the neighborhood of n=70 to n=75 for standard double-precision numbers, which is why a calculator built on this formula needs a documented cutoff rather than claiming unlimited range. Beyond that point, exact results require either arbitrary-precision arithmetic or falling back to the plain iterative recurrence, which never accumulates rounding error in the first place because it only ever adds two exact integers together.

It's a useful reminder that "closed form" and "always the better tool" aren't the same thing. For a single, large, one-off term, the direct formula is faster and conceptually cleaner than looping through every earlier value. For generating a full sequence, or for guaranteeing exactness past the point where floating-point rounding becomes a concern, the plain iterative recurrence is actually the more robust choice — which is exactly why a well-built calculator uses each approach for the job it's suited to, rather than treating one as strictly superior to the other.

The same closed-form technique extends directly to the Lucas sequence, Fibonacci's lesser-known sibling — L(n) = φⁿ + ψⁿ, using the same two roots with a plus sign instead of a minus. You can see both the direct formula and the sequence-building approach in action with the Fibonacci calculator and the Lucas number calculator.