1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci Sequence Induction Problem

  1. May 2, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that for all n greater than 1:

    fn = [itex]\frac{1}{\sqrt{5}}[/itex]{([itex]\frac{1+\sqrt{5}}{2}[/itex])n - ([itex]\frac{1-\sqrt{5}}{2}[/itex])n}


    2. Relevant equations
    f1 = f2= 1
    fn+2 = fn+1 + fn


    3. The attempt at a solution
    I'm pretty sure it's by induction, but I'm not sure how to start.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. May 2, 2012 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What do you need in a proof by induction?
     
  4. May 2, 2012 #3
    What do you mean by what do I need?
     
  5. May 2, 2012 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What's the basic structure of an induction proof? You should be able to at least start the proof.
     
  6. May 3, 2012 #5
    Well what I have done so far is input n+1 and n into the given expression to give:
    fn+1 + fn = [itex]\frac{1}{\sqrt{5}}[/itex] {[[itex]\frac{1+\sqrt{5}}{2}[/itex]]n+1 - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n+1 + [[itex]\frac{1+\sqrt{5}}{2}[/itex]]n - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n}

    I need to make this equal to (in order to prove by induction):
    fn+2 = [itex]\frac{1}{\sqrt{5}}[/itex] {[[itex]\frac{1+\sqrt{5}}{2}[/itex]]n+2 - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n+2}
     
  7. May 3, 2012 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Hint: What's ##\big(\frac{1\pm\sqrt{5}}{2}\big)^2##?
     
  8. May 3, 2012 #7
    Does it have something to do with the quadratic formula?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fibonacci Sequence Induction Problem
  1. Fibonacci sequence (Replies: 5)

  2. Fibonacci Sequence (Replies: 8)

  3. Fibonacci Sequence (Replies: 13)

Loading...