Fibonacci Proof with Induction

[shane1]

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

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

 

[HallsofIvy]

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 f₃²- f_{2[/sup]²= f1f4. Of course, f1= 1,f2= 1, f3= 2, f4= 3 so that just says
2²- 1²= 1*3 which is true.
Since that involves numbers less than just n-1, "strong induction" will probably work better. Assume that fk+2²- fk+1²= fkfk+3 for some k. Then we need to show that fk+3²- fk+2²= 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.}