Difference between revisions of "Binet's Formula"

m (Proof)
m
Line 27: Line 27:
 
&\dots
 
&\dots
 
\end{align*}</cmath>
 
\end{align*}</cmath>
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σnτn=fn(στ)+fn1fn1(1+52)n(152)n=fn(1+52152)  
+
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<cmath>σnτn=fn(στ)+fn1fn1(1+52)n(152)n=fn(1+52152)</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>
+
This yields the general form for the nth 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>
  
 
==See Also==
 
==See Also==
 
*[[Fibonacci number]]
 
*[[Fibonacci number]]
 
[[Category:Theorems]]
 
[[Category:Theorems]]

Revision as of 18:09, 6 November 2018

Binet's formula is an explicit formula used to find the $n$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 $F_n$ is the $n$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)\].

Proof

Written by Mathlete2017

To derive a general formula for the Fibonacci numbers, we can look at the interesting quadratic\[x^2-x-1=0.\]Begin by noting that the roots of this quadratic are $\frac{1\pm\sqrt{5}}{2}$ according to the quadratic formula. This quadratic can also be written as\[x^2=x+1.\] From this, we can write expressions for all $x^n$: \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}.\]Let the roots of our original quadratic be $\sigma=\frac{1+\sqrt 5}{2}$ and $\tau=\frac{1-\sqrt 5}{2}.$ Since both $\sigma$ and $\tau$ are roots of the quadratic, they must both satisfy $x^n=f_nx+f_{n-1}.$ So\[\sigma^n=f_n\sigma+f_{n-1}\]and\[\tau^n=f_n\tau+f_{n-1}.\]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 nth Fibonacci number:\[\boxed{f_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}\]

See Also