Difference between revisions of "Binet's Formula"
Mathlete2017 (talk | contribs) m (→Proof) |
Mathlete2017 (talk | contribs) m (→Proof) |
||
| Line 7: | Line 7: | ||
==Proof== | ==Proof== | ||
| − | To derive a general formula for the Fibonacci numbers, we can look at the interesting quadratic<cmath>x^2-x-1=0.</cmath>Begin by noting that the roots of this quadratic are <math>\frac{1\pm\sqrt{5}}{2}</math> according to the quadratic formula. This quadratic can also be written as<cmath>x^2=x+1.</cmath> From this, we can write expressions for all <math>x^n</math>:\begin{align | + | To derive a general formula for the Fibonacci numbers, we can look at the interesting quadratic<cmath>x^2-x-1=0.</cmath>Begin by noting that the roots of this quadratic are <math>\frac{1\pm\sqrt{5}}{2}</math> according to the quadratic formula. This quadratic can also be written as<cmath>x^2=x+1.</cmath> From this, we can write expressions for all <math>x^n</math>: |
| + | \begin{align} | ||
x&= x\\ | x&= x\\ | ||
x^2 &= x+1\\ | x^2 &= x+1\\ | ||
| Line 23: | Line 24: | ||
x^6 &= 8x+5\\ | x^6 &= 8x+5\\ | ||
&\dots | &\dots | ||
| − | \end{align | + | \end{align} |
We note that<cmath>x^n=f_nx+f_{n-1}.</cmath>Let the roots of our original quadratic be <math>\sigma=\frac{1+\sqrt 5}{2}</math> and <math>\tau=\frac{1-\sqrt 5}{2}.</math> Since both <math>\sigma</math> and <math>\tau</math> are roots of the quadratic, they must both satisfy <math>x^n=f_nx+f_{n-1}.</math> So<cmath>\sigma^n=f_n\sigma+f_{n-1}</cmath>and<cmath>\tau^n=f_n\tau+f_{n-1}.</cmath>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*} | We note that<cmath>x^n=f_nx+f_{n-1}.</cmath>Let the roots of our original quadratic be <math>\sigma=\frac{1+\sqrt 5}{2}</math> and <math>\tau=\frac{1-\sqrt 5}{2}.</math> Since both <math>\sigma</math> and <math>\tau</math> are roots of the quadratic, they must both satisfy <math>x^n=f_nx+f_{n-1}.</math> So<cmath>\sigma^n=f_n\sigma+f_{n-1}</cmath>and<cmath>\tau^n=f_n\tau+f_{n-1}.</cmath>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:<cmath>\boxed{f_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}</cmath> | This yields the general form for the n[sup]th[/sup] Fibonacci number:<cmath>\boxed{f_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}</cmath> | ||
Revision as of 18:04, 6 November 2018
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
![\[F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\]](http://latex.artofproblemsolving.com/8/6/d/86d486c560727727342090b432e23ba85ac098b1.png)
.
Proof
To derive a general formula for the Fibonacci numbers, we can look at the interesting quadratic![\[x^2-x-1=0.\]](http://latex.artofproblemsolving.com/c/f/a/cfa5a22c7b55b2d1d0abf20af16e444b5c4a9961.png)
Begin by noting that the roots of this quadratic are 
according to the quadratic formula. This quadratic can also be written as![\[x^2=x+1.\]](http://latex.artofproblemsolving.com/d/2/8/d2896c78375da247be341cb6fe96e4c0566f27b2.png)
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![\[x^n=f_nx+f_{n-1}.\]](http://latex.artofproblemsolving.com/c/e/9/ce9a0778add037e87c6fe4c64cebc5a1d3cca634.png)
Let the roots of our original quadratic be 
and 
Since both 
and 
are roots of the quadratic, they must both satisfy 
So![\[\sigma^n=f_n\sigma+f_{n-1}\]](http://latex.artofproblemsolving.com/3/d/c/3dc76be6448594fd8a892763b26477c39dd13f57.png)
and![\[\tau^n=f_n\tau+f_{n-1}.\]](http://latex.artofproblemsolving.com/0/e/8/0e84b1cfa080fdb7b7a0ff5f0f4775d16eb0f6f6.png)
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:![\[\boxed{f_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}\]](http://latex.artofproblemsolving.com/8/f/b/8fb1994632f304bcb807c88ed5086904c83e7efa.png)
