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 Calculus)
(→‎Proof using Calculus)
Line 59: Line 59:
 
Recall Maclaurin series: <cmath>\sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!}x^n</cmath>
 
Recall Maclaurin series: <cmath>\sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!}x^n</cmath>
 
Since we broke it down into two simple fractions, now we can plug it into the formula.
 
Since we broke it down into two simple fractions, now we can plug it into the formula.
−
<cmath>F_n=-\left(\frac{s_0}{r_0^{n-1}}+\frac{s_1}{r_1^{n-1}}\right)</cmath>
+
<cmath>F_n=-\left(\frac{s_0}{r_0^{n+1}}+\frac{s_1}{r_1^{n+1}}\right)</cmath>
 
This is a formula, but not Binet's. Or is it?
 
This is a formula, but not Binet's. Or is it?
−
<cmath>F_n=-\left(\frac{\left(\frac{-5+\sqrt{5}}{10}\right)}{\left(\frac{-1+\sqrt{5}}{2}\right)^{n-1}}+\frac{\left(\frac{-5-\sqrt{5}}{10}\right)}{\left(\frac{-1-\sqrt{5}}{2}\right)^{n-1}}\right)</cmath>
+
<cmath>F_n=-\left(\frac{\left(\frac{-5+\sqrt{5}}{10}\right)}{\left(\frac{-1+\sqrt{5}}{2}\right)^{n+1}}+\frac{\left(\frac{-5-\sqrt{5}}{10}\right)}{\left(\frac{-1-\sqrt{5}}{2}\right)^{n+1}}\right)</cmath>
 +
 
 +
First, replacing their reciprocals it with the familiar <math>\phi</math> and <math>\psi</math>.
 +
 
 +
<cmath>F_n=-\left(\left(\frac{-5+\sqrt{5}}{10}\right)\phi^{n+1}+\left(\frac{-5-\sqrt{5}}{10}\right)\psi^{n+1}\right)</cmath>
 +
 
 +
Next: Replacing to the power of n+1 with to the power of n.
 +
 
 +
<cmath>F_n=-\left(\left(\frac{-5+\sqrt{5}}{10}\phi\right)\phi^{n}+\left(\frac{-5-\sqrt{5}}{10}\psi\right)\psi^{n}\right)</cmath>
 +
 
 +
Then: Getting rid of the annoying minus and simplifying.
 +
 
 +
<cmath>F_n=\left(\left(\frac{1}{\sqrt{5}}\right)\phi^{n}+\left(\frac{-1}{\sqrt{5}}\right)\psi^{n}\right)</cmath>
 +
 
 +
Last: Factoring out.
 +
 
 +
<cmath>F_n=\frac{1}{\sqrt{5}}\left(\phi^{n}-\psi^{n})</cmath>
 +
 
 +
Yay! We did it! [[User:Afly|Afly]] ([[User talk:Afly|talk]])afly (very good at calculus)
 +
P.S. I discovered this proof while trying to come up with a closed form formula by myself
  
 
==See Also==
 
==See Also==
 
*[[Fibonacci number]]
 
*[[Fibonacci number]]
 
[[Category:Theorems]]
 
[[Category:Theorems]]

Revision as of 20:32, 30 May 2024

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

Proof using Calculus

The fibonacci sequence is defined as follows: \[F_0=0,~F_1=1,~F_n+F_{n+1}=F_{n+2}\] We can write a power series: \[f(x)=\sum_{n=0}^{\infty} F_n x^n\] It's coefficients look like this: 

0 1 1 2 3 5 8 ...

Coefficients for: 

f(x)-x 0 0 1 2 3 5 8 ...
x f(x) 0 0 1 1 2 3 5 ...
x²f(x) 0 0 0 1 1 2 3 ...

\[f(x)-x=xf(x)+x^2f(x) \text{ so } f(x)=\frac{x}{1-x-x^2}\] Minor technical point: This will only converge if \[|x|<\frac{\sqrt{5}-1}{2}\] but we will only evaluate at 0.

Then, we can take partial fractions! \[\left(\frac{s_0}{x-r_0}+\frac{s_1}{x-r_1}\right)\] \[r_0,r_1=\frac{-1\pm\sqrt{5}}{2},s_0,s_1=\frac{-5\pm\sqrt{5}}{10}\]

It is known that the nth derivative of \[\frac{r}{x-s}\] is \[(-1)^{n}n!\frac{r}{(x-s)^{n+1}}\] Hint: let u=x-s and use the chain rule.

Recall Maclaurin series: \[\sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!}x^n\] Since we broke it down into two simple fractions, now we can plug it into the formula. \[F_n=-\left(\frac{s_0}{r_0^{n+1}}+\frac{s_1}{r_1^{n+1}}\right)\] This is a formula, but not Binet's. Or is it? \[F_n=-\left(\frac{\left(\frac{-5+\sqrt{5}}{10}\right)}{\left(\frac{-1+\sqrt{5}}{2}\right)^{n+1}}+\frac{\left(\frac{-5-\sqrt{5}}{10}\right)}{\left(\frac{-1-\sqrt{5}}{2}\right)^{n+1}}\right)\]

First, replacing their reciprocals it with the familiar $\phi$ and $\psi$.

\[F_n=-\left(\left(\frac{-5+\sqrt{5}}{10}\right)\phi^{n+1}+\left(\frac{-5-\sqrt{5}}{10}\right)\psi^{n+1}\right)\]

Next: Replacing to the power of n+1 with to the power of n.

\[F_n=-\left(\left(\frac{-5+\sqrt{5}}{10}\phi\right)\phi^{n}+\left(\frac{-5-\sqrt{5}}{10}\psi\right)\psi^{n}\right)\]

Then: Getting rid of the annoying minus and simplifying.

\[F_n=\left(\left(\frac{1}{\sqrt{5}}\right)\phi^{n}+\left(\frac{-1}{\sqrt{5}}\right)\psi^{n}\right)\]

Last: Factoring out. 

\[F_n=\frac{1}{\sqrt{5}}\left(\phi^{n}-\psi^{n})\] (Error compiling LaTeX. Unknown error_msg)

Yay! We did it! Afly (talk)afly (very good at calculus) P.S. I discovered this proof while trying to come up with a closed form formula by myself

See Also

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