Fibonacci Sequence Induction Problem

blak97
Messages
5
Reaction score
0

Homework Statement


Show that for all n greater than 1:

fn = \frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})n - (\frac{1-\sqrt{5}}{2})n}


Homework Equations


f1 = f2= 1
fn+2 = fn+1 + fn


The Attempt at a Solution


I'm pretty sure it's by induction, but I'm not sure how to start.
 
Physics news on Phys.org
What do you need in a proof by induction?
 
What do you mean by what do I need?
 
What's the basic structure of an induction proof? You should be able to at least start the proof.
 
Well what I have done so far is input n+1 and n into the given expression to give:
fn+1 + fn = \frac{1}{\sqrt{5}} {[\frac{1+\sqrt{5}}{2}]n+1 - [\frac{1-\sqrt{5}}{2}]n+1 + [\frac{1+\sqrt{5}}{2}]n - [\frac{1-\sqrt{5}}{2}]n}

I need to make this equal to (in order to prove by induction):
fn+2 = \frac{1}{\sqrt{5}} {[\frac{1+\sqrt{5}}{2}]n+2 - [\frac{1-\sqrt{5}}{2}]n+2}
 
Hint: What's ##\big(\frac{1\pm\sqrt{5}}{2}\big)^2##?
 
Does it have something to do with the quadratic formula?
 

Similar threads

Replies
1
Views
1K
Replies
7
Views
2K
Replies
8
Views
2K
Replies
15
Views
2K
Replies
5
Views
4K
Replies
1
Views
1K
Replies
3
Views
1K
Replies
6
Views
3K
Back
Top