Fibonacci Numbers and Recursion - psholtz/MIT-SICP GitHub Wiki
Exercise 1.13
Prove that Fib(n) is the closest integer to
where
Solution
It is worth noting that the linear operator defining the Fibonacci sequence is given by:
and that the eigenvalues of this operator are given by:
It is worth noting further that phi so defined is the famous golden ratio or golden mean.
First, let's show that:
which, even on its own, is a pretty cool formula (see also Fibonacci Numbers and Linear Operators).
We proceed by induction.
Beginning with Fib(n) as defined by the procedure:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2)))))
it is easily verified that:
and that
To prove the formula for higher n, we evaluate the expression for Fib(n) + Fib(n-1) and see whether it reduces to the expression we expect for Fin(n+1):
But by the definition of Fibonacci numbers, we must also have:
and so we conclude that:
In other words, if the expression holds true for Fib(n-1) and it holds true for Fib(n), it must hold true for Fib(n+1) as well, and the proof is established by induction.
Next, consider the expression:
Clearly, 0 = Fib(0) is the closest integer to this value.
Similarly, for n=1, we have:
and 1 = Fib(1) is the closest integer to this value.
For arbitrary n > 1, we have:
where
and so for n > 1, we must have:
which was to be proved.