Is there a faster way to compute the nth Fibonacci number than by fib2? Hint: One idea involves matrices.

There exists a (log n) algorithm for computing the nth Fibonacci number that manipulates only integers. It is based on the equality

F_n-1 F_n 0 1 ⁿ

= for n 1. (it is a matrix)

F_n F_n+1 1 1

Prove the equality.