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.