# Fibonacci Proof with Induction

1. Apr 14, 2006

### 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 [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. Apr 14, 2006

### HallsofIvy

Staff Emeritus
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.