mathschallenge.net

Problem

Given the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, ... defined by the second order recurrence relation, F_n+2 = F_n + F_n+1. Prove that the nth term, F_n, is given by:

Fn =

1 5

1 + 5 2

n

1 5 2

n