## Fibonacci Sequence

#### 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 `n`th term, `F`_{n}, is given by:

F_{n} = | 1 5 | 1 + 5 2 | ^{n} | 1 5 2 | ^{n} |

Problem ID: 135 (Nov 2003) Difficulty: 4 Star