Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Binet's Formula"

(→‎Proof using Recursion)
m (grammar: it's --> its)
Line 31: Line 31:
  
 
==Proof using Recursion==
 
==Proof using Recursion==
−
The Fibonacci recursive relation is <math>F_n = F_{n-1} + F_{n-2}.</math> This is a constant coefficient linear homogenous recurrence relation. We also know that <math>F_0 = 0</math> and <math>F_1 = 1.</math> Thus, it’s characteristic equation is <math>x^2-x-1=0</math> which has solutions <cmath>\frac{1\pm\sqrt{5}}{2}.</cmath>Let <math>v= \frac{1+\sqrt{5}}{2}</math> and <math>p= \frac{1-\sqrt{5}}{2}.</math> We get that <cmath>F_n = \lambda_1 v^n + \lambda_2 p^n.</cmath>Plugging in our initial conditions, we get
+
The Fibonacci recursive relation is <math>F_n = F_{n-1} + F_{n-2}.</math> This is a constant coefficient linear homogenous recurrence relation. We also know that <math>F_0 = 0</math> and <math>F_1 = 1.</math> Thus, its characteristic equation is <math>x^2-x-1=0</math> which has solutions <cmath>\frac{1\pm\sqrt{5}}{2}.</cmath>Let <math>v= \frac{1+\sqrt{5}}{2}</math> and <math>p= \frac{1-\sqrt{5}}{2}.</math> We get that <cmath>F_n = \lambda_1 v^n + \lambda_2 p^n.</cmath>Plugging in our initial conditions, we get
  
 
<cmath>0 = \lambda_1 + \lambda_2 </cmath> <cmath> 1= \lambda_1 v + \lambda_2 p </cmath>
 
<cmath>0 = \lambda_1 + \lambda_2 </cmath> <cmath> 1= \lambda_1 v + \lambda_2 p </cmath>

Revision as of 12:34, 26 November 2023

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

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}}\]


Proof using Recursion

The Fibonacci recursive relation is $F_n = F_{n-1} + F_{n-2}.$ This is a constant coefficient linear homogenous recurrence relation. We also know that $F_0 = 0$ and $F_1 = 1.$ Thus, its characteristic equation is $x^2-x-1=0$ which has solutions \[\frac{1\pm\sqrt{5}}{2}.\]Let $v= \frac{1+\sqrt{5}}{2}$ and $p= \frac{1-\sqrt{5}}{2}.$ We get that \[F_n = \lambda_1 v^n + \lambda_2 p^n.\]Plugging in our initial conditions, we get

\[0 = \lambda_1 + \lambda_2\] \[1= \lambda_1 v + \lambda_2 p\]

Since $0 = \lambda_1 + \lambda_2 \implies 0 = \lambda_1 v+ \lambda_2 v,$ subtracting $0 = \lambda_1 v+ \lambda_2 v$ from $1 = \lambda_1 v + \lambda_2 p,$ we get $1 = \lambda_2(p-v) \implies \lambda_2 = \frac{1}{p-v} = -\frac{1}{\sqrt{5}}.$ Since $\lambda_2 = -\frac{1}{\sqrt{5}}$ and $0 = \lambda_1 + \lambda_2,$ $\lambda_1 = \frac{1}{\sqrt{5}}.$ Therefore, \[F_n = \lambda_1 v^n + \lambda_2 p^n \implies F_n = \left (\frac{1}{\sqrt{5}} \right ) v^n + \left (-\frac{1}{\sqrt{5}} \right ) p^n.\]Therefore, the general form of the $n$th Fibonacci number is \[\boxed{F_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}\] ~peelybonehead

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula&oldid=205889"