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.