Theorem: Fib(n) is the closest integer to phi^n/sqrt(5) where phi = (1 + sqrt(5))/2 and Fib(n) = 0 if n = 0 1 if n = 1 Fib(n - 1) + Fib(n - 2) if n > 1 Let psi = (1 - sqrt(5))/2 Lemma: Fib(n) = (phi^n - psi^n)/sqrt(5) Proof: case n = 0 (phi^0 - psi^0)/sqrt(5) = 0 = Fib(0) case n = 1 (phi^1 - psi^1)/sqrt(5) = ((1 + sqrt(5))/2 - (1 - sqrt(5))/2)/sqrt(5) = (2*sqrt(5)/2)/sqrt(5) = 1 = Fib(1) Suppose the lemma holds for all n' < n phi^2 = (1 + 2*sqrt(5) + 5)/4 = (6 + 2*sqrt(5))/4 = (3 + sqrt(5))/2 = (1 + sqrt(5))/2 + 1 = phi + 1 psi = (1 - 2*sqrt(5) + 5)/4 = (6 - 2*sqrt(5))/4 = (3 - sqrt(5))/2 = (1 - sqrt(5))/2 + 1 = psi + 1 Fib(n) = Fib(n - 1) + Fib(n - 2) = (phi^(n - 1) - psi^(n -1))/sqrt(5) + (phi^(n - 2) - psi^(n - 2))/sqrt(5) = (phi^(n - 2)(phi + 1) - psi^(n - 2)(psi + 1))/sqrt(5) = (phi^(n - 2)phi^2 - psi^(n - 2)psi^2)/sqrt(5) = (phi^n - psi^n)/sqrt(5) Proof of theorem: 2^2 = 4 < 5 < 9 = 3^3 => 2 < sqrt(5) < 3 => -2 < 1 - sqrt(5) < -1 => -1 < psi < -1/2 => 1/2 < -psi < 1 => 1/2^n < (-psi)^n < If n is even: 1/2^n < psi^n < 1 phi^n/sqrt(5) - 1/sqrt(5) < Fib(n) < phi^n/sqrt(5) The interval has width 1/sqrt(5) < 1 => the interval contains a single integer: Fib(n) Fib(n) + 1 > phi^n/sqrt(5) + (1 - 1/sqrt(5)) => Fib(n) is at most 1/sqrt(5) below phi^n/sqrt(5) while Fib(n) + 1 is at least 1 - 1/sqrt(5) above => Fib(n) is the closest integer. If n is odd: 1/2^n < -psi^n < 1 => -1 < psi^n < -1/2^n phi^n/sqrt(5) < Fib(n) < phi^n/sqrt(5) + 1/sqrt(5) => Fib(n) - 1 < phi^n/sqrt(5) + 1/sqrt(5) - 1 => Fib(n) is at most 1/sqrt(5) greater than phi^n/sqrt(5) while Fib(n) +1 is at lest 1 - 1/sqrt(5) less than phi^n/sqrt(5) => Fib(n) is the closest integer.