Fibonacci sequenceDate: 1/28/96 at 11:14:46 From: Kate Bauer and Eric Lindblom Subject: Fibonacci sequence What is the explicit formula for the Fibonacci numbers? Thank you very much for your help, Kate Bauer Date: 6/5/96 at 8:4:27 From: Doctor Charles Subject: Re: Fibonacci sequence There is an explicit formula for the Fibonacci numbers and it involves the Golden Mean (=phi=(1+sqrt(5))/2). However it is very ugly compared to the rest of the Fibonacci sequence's properties. My definition of the sequence starts at 0 but you may prefer 1. 0 is easier to work with in this problem and it is easy to convert back at the end. We have to solve: f_0 = 1 f_1 = 1 f_n = f_n-1 + f_n-2 To solve difference equations like this (the technique is analogous to linear 2nd order differential equations) we first solve the auxiliary equation: k^2 = k + 1 and get k = (1+sqrt(5))/2 or (1-sqrt(5))/2 = phi or (1 - phi) This gives that any sequence of the form f_n = a * (phi)^n + b * (1-phi)^n will satisfy the difference equation: f_n = f_n-1 + f_n-2. You can check this by substituting the formula into the difference equation. Now we just have to find a and b such that f_0 = 1 and f_1 = 1. f_0 = 1 = a + b f_1 = 1 = a * phi + b * (1 - phi). So we get b (2*phi - 1) = phi - 1 and a (2*phi - 1) = phi. but 2*phi - 1 = sqrt 5 so we have f_n = phi/sqrt(5) * (phi)^n + (phi-1)/sqrt5 * (1-phi)^n = phi^(n+1) / sqrt(5) - (1-phi)^(n+1) / sqrt(5) and if you want your sequence to start at 0, not 1, you get the simpler: f_n = phi^n / sqrt(5) - (1-phi)^n / sqrt(5) I hope this helps! -Doctor Charles, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/