Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Derivation of nth fibonacci term

  1. Aug 31, 2008 #1
    i know that there is a formula to find the nth term.
    two questions:

    what does mean for non-integer n (as the recurrence relation breaks down i think),
    and how was this derived
     
  2. jcsd
  3. Sep 1, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The Fibonacci sequence is defined by F0= 1, F1= 1, Fn+2= Fn+1+ Fn.

    A standard method of trying to solve such recursion formulas is to try something of the form Fn= an. Then, of course, Fn+1= an+1 and Fn+2= an+2 so the equation becomes an+2= an+1+ an. If we divide the entire equation by an we arrive at a2= a+ 1 or the quadratic equation a2- a- 1= 0. Solving that by the quadratic formula,
    [tex]a= \frac{1\pm\sqrt{5}}{2}[/tex]
    That tells us that
    [tex]F_n= \left(\frac{1+ \sqrt{5}}{2}\right)^n[/tex]
    and
    [tex]F_n= \left(\frac{1-\sqrt{5}}{2}\right)^n[/tex]
    satisfy that equation. Since this is a linear equation, any solution must be of the form
    [tex]F_n= A\left(\frac{1+ \sqrt{5}}{2}\right)^n+ B\left(\frac{1- \sqrt{5}}{2}\right)^n[/tex]
    for some numbers A and B.
    In particular, if n= 0
    [tex]F_0= A+ B= 1[/itex]
    and, if n= 1
    [tex]F_n= A\left(\frac{1+ \sqrt{5}}{2}\right)+ B\left(\frac{1- \sqrt{5}}{2}\right)= 1[/tex]
    Solving those two equations for A and B, we get (assuming I have done the arithmetic correctly!)
    [tex]A= \frac{1+\sqrt{5}}{2\sqrt{5}}[/tex]
    and
    [tex]B= \frac{1-\sqrt{5}}{2\sqrt{5}}[/tex]

    Putting all of that together, we have
    [tex]F_n= \frac{1+\sqrt{5}}{2\sqrt{5}}\left(\frac{1+ \sqrt{5}}{2}\right)^n+ \frac{1-\sqrt{5}}{2\sqrt{5}}\left(\frac{1- \sqrt{5}}{2}\right)^n[/tex]

    It is remarkable that this gives integer values for n any non-negative integer!

    I don't know that it "means" anything for non-integer n.
     
  4. Sep 1, 2008 #3
    Thank you!
     
  5. Sep 1, 2008 #4

    Borek

    User Avatar

    Staff: Mentor

    I wonder if using formula shown by HallsofIvy is faster than using definition, as raising irrational numbers to high powers with high accuracy is numerically much more expensive then integer addition.
     
  6. Sep 1, 2008 #5
    I don't see how that formula works. It does not work for n=1. I take this, as well as I can write it, to be the standard form:

    [tex]((\frac{1+\sqrt5}{2}})^n-({\frac{1-\sqrt5}{2})^n})*{\frac{1}{\sqrt5}}[/tex]
     
    Last edited: Sep 1, 2008
  7. Sep 2, 2008 #6

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Halls,
    I think you lost a minus sign on the B term should read:

    [tex] F_n= \frac{1+\sqrt{5}}{2\sqrt{5}}\left(\frac{1+ \sqrt{5}}{2}\right)^n- \frac{1-\sqrt{5}}{2\sqrt{5}}\left(\frac{1- \sqrt{5}}{2}\right)^n [/tex]

    Edit may as well finish it.

    This can be written as:

    [tex] F_n = \left(\left(\frac {1+ \sqrt{5}} 2\right)^{n+1} - \left (\frac {1- \sqrt{5}} 2\right)^{n+1} \right)* \frac 1 {\sqrt{5}} [/tex]


    Edit again:
    Robert, you seem to have lost a factor, your exponent should be n+1, it does indeed work with that correction.
     
    Last edited: Sep 2, 2008
  8. Sep 2, 2008 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Dang! If I could only do arithmetic!
     
  9. Sep 2, 2008 #8

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    :rofl: How well I know the feeling.
     
  10. Sep 2, 2008 #9
    Integral, Robert, you seem to have lost a factor, your exponent should be n+1, it does indeed work with that correction.

    It depends upon how we start the series. Wolfram says, F(1) = F(2) = 1.
    http://mathworld.wolfram.com/FibonacciNumber.html.
     
  11. Sep 2, 2008 #10
    Borek: I wonder if using formula shown by HallsofIvy is faster than using definition, as raising irrational numbers to high powers with high accuracy is numerically much more expensive then integer addition.

    One thing that happens here is that the second term goes to zero. Even using this term: [tex](-\frac{1-\sqrt5}{2})^3*(\frac{1}{\sqrt5}) = \succ.11[/tex] (Approximately .11)

    So that we only need to use the closest interger to the first term.
     
  12. Sep 3, 2008 #11

    Borek

    User Avatar

    Staff: Mentor

    It doesn't change much. It is still about log(n) multiplications to calculate nth power. In the end we have n integer additions vs log(n) real multiplications. Or something like that.
     
  13. Sep 3, 2008 #12
    Hey, whoa, it's the golden ratio! Is the way that the golden ratio shows up in your derived formula something that is something special about the Fibonacci sequence compared to other recursive formulas?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Derivation of nth fibonacci term
  1. Fibonacci Primes (Replies: 6)

  2. Nth term (Replies: 1)

Loading...