Exercise 1 shows that it is possible to compute x n in O(log N) time. This fact in turn makes it possible to write an implementation of the function fib(n) that also runs in O(log N) time, which is much faster than the traditional iterative version. To do so, you need to rely on the somewhat surprising fact that the Fibonacci function is closely related to a value called the golden ratio, which has been known since the days of Greek mathematics. The golden ratio, which is usually designated by the Greek letter phi (), is defined to be the value that satisfies the equation

Because this is a quadratic equation, it actually has two roots. If you apply the quadratic formula, you will discover that these roots are

In 1718, the French mathematician Abraham de Mover discovered that the n^th Fibonacci number can be represented in closed form as

Moreover, because ⁿ is always very small, the formula can be simplified to

rounded to the nearest integer. Use this formula and the raiseToPower function from exercise 1 to write an implementation of fib(n) that runs in O(log N) time. Once you have verified empirically that the formula seems to work for the first several terms in the sequence, use mathematical induction to prove that the formula

actually computes the n^th Fibonacci number.