Fibonacci Proof with Induction

  • Thread starter shane1
  • Start date
  • #1
7
0
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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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.
 

Related Threads on Fibonacci Proof with Induction

  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
3K
Replies
11
Views
19K
Replies
7
Views
4K
Replies
7
Views
9K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
1
Views
420
  • Last Post
Replies
2
Views
2K
Top