#| This exercise has no tests.
Any solution is a right answer. |#
; fib(n) is the closest integer to φ^n / sqrt(5)
; where φ = (1 + √5) / 2

; let ψ = (1 - √5) / 2
; prove that fib(n) = (φ^n - ψ^n) / √5

; fib(0) = 0
; (φ^0 - ψ^0) / √5 = (1 - 1) / √5 = 0

; fib(1) = 1
; (φ^1 - ψ^1) / √5 = ((1 + √5) / 2 - (1 - √5) / 2) / √5 =
; = ((1 + √5) - (1 - √5)) / 2) / √5 = ((1 + √5 - 1 + √5) / 2) / √5 =
; = (2√5 / 2) / √5 = 1

; fib(n) = fib(n-1) + fib(n-2)
; (φ^n - ψ^n) / √5 = (φ^n-1 - ψ^n-1) / √5 + (φ^n-2 - ψ^n-2) / √5
; φ^n - ψ^n = φ^n-1 - ψ^n-1 + φ^n-2 - ψ^n-2
; φ^n - ψ^n = φ^n/φ - ψ^n/ψ + φ^n/φ^2 - ψ^n/ψ^2
; φ^n - ψ^n = φ^n(1/φ + 1/φ^2) - ψ^n(1/ψ + 1/ψ^2)
; φ^n - ψ^n = φ^n(1/(1 + √5) / 2 + 1/((1 + √5) / 2)^2) - ψ^n(1/ψ + 1/ψ^2)