Difference between revisions of "Binet's Formula"
(→Proof) |
(→Proof using Calculus) |
||
(8 intermediate revisions by 5 users not shown) | |||
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, | + | 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 | ~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 21:37, 30 May 2024
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
.
Proof
To derive a general formula for the Fibonacci numbers, we can look at the interesting quadraticBegin by noting that the roots of this quadratic are
according to the quadratic formula. This quadratic can also be written as
From this, we can write expressions for all
:
We note that
Let the roots of our original quadratic be
and
Since both
and
are roots of the quadratic, they must both satisfy
So
and
Subtracting the second equation from the first equation yields
This yields the general form for the nth Fibonacci number:
Proof using Recursion
The Fibonacci recursive relation is This is a constant coefficient linear homogenous recurrence relation. We also know that
and
Thus, its characteristic equation is
which has solutions
Let
and
We get that
Plugging in our initial conditions, we get
Since subtracting
from
we get
Since
and
Therefore,
Therefore, the general form of the
th Fibonacci number is
~peelybonehead
Proof using Calculus
The fibonacci sequence is defined as follows:
We can write a power series:
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 ...
Minor technical point: This will only converge if
but we will only evaluate at 0.
Then, we can take partial fractions!
It is known that the nth derivative of is
Hint: let u=x-s and use the chain rule.
Recall Maclaurin series:
Since we broke it down into two simple fractions, now we can plug it into the formula.
This is a formula, but not Binet's. Or is it?
First, replacing their reciprocals it with the familiar and
.
Next: Replacing to the power of n+1 with to the power of n.
Then: Getting rid of the annoying minus and simplifying.
Last: Factoring out.
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