# Homework Help: Fibonacci Sequence Induction Problem

1. May 2, 2012

### blak97

1. The problem statement, all variables and given/known data
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}

2. Relevant equations
f1 = f2= 1
fn+2 = fn+1 + fn

3. The attempt at a solution
I'm pretty sure it's by induction, but I'm not sure how to start.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. May 2, 2012

### vela

Staff Emeritus
What do you need in a proof by induction?

3. May 2, 2012

### blak97

What do you mean by what do I need?

4. May 2, 2012

### vela

Staff Emeritus
What's the basic structure of an induction proof? You should be able to at least start the proof.

5. May 3, 2012

### blak97

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}

6. May 3, 2012

### vela

Staff Emeritus
Hint: What's $\big(\frac{1\pm\sqrt{5}}{2}\big)^2$?

7. May 3, 2012

### blak97

Does it have something to do with the quadratic formula?