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.

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

    HallsofIvy

    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