Difference between revisions of "Binet's Formula"

Revision as of 21:21, 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)$

@@ Line 39: / Line 39: @@
 ==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:
+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>
 ==See Also==
 *[[Fibonacci number]]
 [[Category:Theorems]]

Page

Toolbox

Search