sicp exercise 1.13

; Exercise 1.13.  Prove that Fib(n) is the closest integer to ⁿ/5, where = (1 + 5)/2.
; Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see
; section 1.2.2) to prove that Fib(n) = (ⁿ - ⁿ)/5.

; Answer:

; p =   s =

; Fib(n) = Fib(n-1) + Fib(n-2)
; p^n - s^n = p^(n-1) - s^(n-1) + p^(n-2) + s^(n-2)
;           = p^(n-2) ( p + 1) - s^(n-2) (s + 1)
;   since 1 + p = p^2 and 1 + s = s^2
;           = p^n - s^n