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 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:
    [​IMG]

    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
     
  2. jcsd
  3. Apr 14, 2006 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Fibonacci Proof with Induction
Loading...