Fibonacci Sequence Induction Problem

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}

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.

The Attempt at a Solution

Related Calculus and Beyond Homework Help News on Phys.org
vela
Staff Emeritus
Homework Helper
What do you need in a proof by induction?

What do you mean by what do I need?

vela
Staff Emeritus
Homework Helper
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}

vela
Staff Emeritus