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"

m
(→‎Proof using Calculus)
 
(18 intermediate revisions by 9 users not shown)
Line 7: Line 7:
  
 
==Proof==
 
==Proof==
−
If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach <math>1.618\ldots</math>: <math>\frac{1}{1} = 1, \frac{2}{1} = 2, \frac{3}{2} = 1.5, \ldots, \frac{34}{21} \approx 1.617, \frac{55}{34} \approx 1.618, \ldots</math>. Thus we have a sequence resembling that of a [[geometric sequence]]. We let such a geometric sequence have terms <math>G_n = a \cdot r^n</math>. Then, <math>F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1} </math> <math>\Longrightarrow r^2 = r + 1</math>. Using the [[quadratic formula]], we find <math>r = \frac{1 \pm \sqrt{5}}{2}</math>.
 
  
−
We now have two sequences <math>G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n</math> and <math>H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n</math>, but neither match up with the Fibonacci sequence. In particular, <math>F_0 = 0</math>, but for <math>G_0, H_0</math> to be zero, we need <math>a = 0</math>, but then the sequence just generates a constant <math>0</math>. After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that <math>G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}</math>, so <math>G_{n} - H_{n}</math> also satisfies this recurrence. If we match up the numbers of <math>F_n</math> and <math>G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>, we note that <math>F_0 = G_0 - H_0 = 0</math>. However, <math>F_1 = 1 = G_1 - H_1</math>, which implies that <math>a = \frac{1}{\sqrt{5}}</math>. Now, <math>G_n - H_n</math> satisfies the same recurrence as <math>F_n</math> and has the same initial terms, so we are done.
+
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>:
 +
<cmath>\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*}</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<cmath>\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*}</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>
 +
 
 +
 
 +
==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, 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>
 +
 
 +
Since <math>0 = \lambda_1 + \lambda_2 \implies 0 = \lambda_1 v+ \lambda_2 v,</math> subtracting <math>0 = \lambda_1 v+ \lambda_2 v</math> from <math>1 = \lambda_1 v + \lambda_2 p,</math> we get <math>1 = \lambda_2(p-v) \implies \lambda_2 = \frac{1}{p-v} = -\frac{1}{\sqrt{5}}.</math> Since <math>\lambda_2 = -\frac{1}{\sqrt{5}}</math> and <math>0 = \lambda_1 + \lambda_2,</math> <math>\lambda_1 = \frac{1}{\sqrt{5}}.</math> Therefore, <cmath>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.</cmath>Therefore, the general form of the <math>n</math>th Fibonacci number is <cmath>\boxed{F_n = \frac{\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}}</cmath>
 +
~peelybonehead
 +
 
 +
==Proof using Calculus==
 +
 
 +
The fibonacci sequence is defined as follows: <cmath>F_0=0,~F_1=1,~F_n+F_{n+1}=F_{n+2}</cmath>
 +
We can write a power series: <cmath>f(x)=\sum_{n=0}^{\infty} F_n x^n</cmath>
 +
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 ...
 +
<cmath>f(x)-x=xf(x)+x^2f(x) \text{ so } f(x)=\frac{x}{1-x-x^2}</cmath>
 +
Minor technical point: This will only converge if <cmath>|x|<\frac{\sqrt{5}-1}{2}</cmath> but we will only evaluate at 0.
 +
 
 +
Then, we can take partial fractions! <cmath>\left(\frac{s_0}{x-r_0}+\frac{s_1}{x-r_1}\right)</cmath>
 +
<cmath>r_0,r_1=\frac{-1\pm\sqrt{5}}{2},s_0,s_1=\frac{-5\pm\sqrt{5}}{10}</cmath>
 +
 
 +
It is known that the nth derivative of <cmath>\frac{r}{x-s}</cmath> is <cmath>(-1)^{n}n!\frac{r}{(x-s)^{n+1}}</cmath>
 +
Hint: let u=x-s and use the chain rule.
 +
 
 +
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.
 +
<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?
 +
<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>\text{Note: }\phi=\frac{1+\sqrt{5}}{2},~\psi=\frac{1-\sqrt{5}}{2}</cmath>
 +
 
 +
<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}\right)</cmath>
 +
 
 +
Yay! We did it! [[User:Afly|Afly]] ([[User talk:Afly|talk]]) (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]]

Latest revision as of 20:37, 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$.

\[\text{Note: }\phi=\frac{1+\sqrt{5}}{2},~\psi=\frac{1-\sqrt{5}}{2}\]

\[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}\right)\]

Yay! We did it! Afly (talk) (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=219911"