Binet's Formula
Binet's formula is an explicit formula used to find the th term of the Fibonacci sequence.
It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre.
Formula
If is the
th Fibonacci number, then
.
Proof
To derive a general formula for the Fibonacci numbers, we can look at the interesting quadraticBegin by noting that the roots of this quadratic are
according to the quadratic formula. This quadratic can also be written as
From this, we can write expressions for all
:
\begin{align}
x&= x\\
x^2 &= x+1\\
x^3 &= x\cdot x^2\\
&= x\cdot (x+1)\\
&= x^2+x\\
&= (x+1) + x\\
&= 2x+1\\
x^4 &= x \cdot x^3\\
&= x\cdot (2x+1)\\
&= 2x^2+x\\
&=2(x+1)+x\\
&=3x+2\\
x^5 &= 5x+3\\
x^6 &= 8x+5\\
&\dots
\end{align}
We note that
Let the roots of our original quadratic be
and
Since both
and
are roots of the quadratic, they must both satisfy
So
and
Subtracting the second equation from the first equation yields\begin{align*}\sigma^n-\tau^n=f_n(\sigma-\tau)+f_{n-1}-f_{n-1} \\ \left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n = f_n \left(\frac{1+\sqrt 5}{2} - \frac{1-\sqrt 5}{2}\right)\end{align*}
This yields the general form for the n[sup]th[/sup] Fibonacci number: