1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Fibonacci Proof with Induction

  1. Apr 14, 2006 #1
    I'm working on a question as stated above for my computer science course. Since the topic was taken the Fibonacci numbers have puzzled me with their laws for simplification etc...

    Here is the question:
    http://img404.imageshack.us/img404/7668/fib0au.png [Broken]

    I'm not sure where to start with it whether I should use standard induction or strong induction to prove it.

    Any help would be apreciated.

    PS if this is in the wrong place then move it.

    Last edited by a moderator: May 2, 2017
  2. jcsd
  3. Apr 14, 2006 #2


    User Avatar
    Science Advisor

    Well, start it and then decide whether to use regular or strong induction. Whichever you use, you will need to prove the "base" case:
    with n= 1 you want to show that f32- f2[/sup]2= f1f4. Of course, f1= 1,f2= 1, f3= 2, f4= 3 so that just says
    22- 12= 1*3 which is true.
    Since that involves numbers less than just n-1, "strong induction" will probably work better. Assume that fk+22- fk+12= fkfk+3 for some k. Then we need to show that fk+32- fk+22= fk+1fk+4. By definition of Fibonacci sequence, fk+4= fk+2+ fk+1, fk+3= fk+1+ fk+2, fk+2= fk+ fk+1, fk+1= fk+ fk+1 so try putting those in.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook