• Support PF! Buy your school textbooks, materials and every day products Here!

Fibonacci Sequence Induction Problem

  • Thread starter blak97
  • Start date
  • #1
5
0

Homework Statement


Show that for all n greater than 1:

fn = [itex]\frac{1}{\sqrt{5}}[/itex]{([itex]\frac{1+\sqrt{5}}{2}[/itex])n - ([itex]\frac{1-\sqrt{5}}{2}[/itex])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.

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
What do you need in a proof by induction?
 
  • #3
5
0
What do you mean by what do I need?
 
  • #4
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
What's the basic structure of an induction proof? You should be able to at least start the proof.
 
  • #5
5
0
Well what I have done so far is input n+1 and n into the given expression to give:
fn+1 + fn = [itex]\frac{1}{\sqrt{5}}[/itex] {[[itex]\frac{1+\sqrt{5}}{2}[/itex]]n+1 - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n+1 + [[itex]\frac{1+\sqrt{5}}{2}[/itex]]n - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n}

I need to make this equal to (in order to prove by induction):
fn+2 = [itex]\frac{1}{\sqrt{5}}[/itex] {[[itex]\frac{1+\sqrt{5}}{2}[/itex]]n+2 - [[itex]\frac{1-\sqrt{5}}{2}[/itex]]n+2}
 
  • #6
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
Hint: What's ##\big(\frac{1\pm\sqrt{5}}{2}\big)^2##?
 
  • #7
5
0
Does it have something to do with the quadratic formula?
 

Related Threads on Fibonacci Sequence Induction Problem

Replies
11
Views
19K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
15K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
13
Views
3K
Top