Difference between revisions of "Binet's Formula"
(→Proof) |
(→Proof using Recursion) |
||
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, 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 |
+ | |||
+ | <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 | ||
Revision as of 17:55, 19 May 2023
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 thatLet the roots of our original quadratic be and Since both and are roots of the quadratic, they must both satisfy SoandSubtracting 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, it’s 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