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

Homework Help: 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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook