For the last couple of months, I have been working though the
exercises in Structure
and Interpretation of Computer Programs by Abelson and Sussman.
I generally try not to skip any exercises but every now and then I
encounter one that is a bit too difficult. Today I return to a question
from the first chapter that I had originally skipped.
Here Fib(n) denotes the n-th number in the
Fibonacci sequence (1, 1, 2, 3, 5, … , Fib(n)). My approach
follows the hint in the question and proves that Fib(n) differs
from phi^n/sqrt(5) by less than one-half for all natural
numbers n.
I may have been a bit on the long-winded side but I believe the proof is correct. Please enjoy and do not hesitate to contact me if you spot any errors.