1.13 Exercise 1.13
Statement: Fib(n) is the closest integer to (ø^n) / √5, where ø = (1 + √5) / 2.
Hint: Let ψ = (1 - √5) / 2. The closest integer is then (ø^n - ψ^n) / √5.
Base case: n = 0.
Fib(0) = (Ø^0 - ψ^0) / √5 = 0 |
Inductive case: Assume the statement holds for all k up to n. Prove that it holds for n + 1.
Note that, by the definition of Fib, Fib(k + 1) = Fib(k) + Fib(k - 1). So,
(ø^(k+1) - ψ^(k+1)) / √5 = (ø^k - ψ^k) / √5 + (ø^(k-1) - ψ^(k-1)) / √5 |
Multiplying both sides by √5 and rearranging, we get
ø^(k+1) - ψ^(k+1) = ø^k + ø^(k-1) - ψ^k - ψ^(k-1) |
ø^(k-1) * ø^2 - ψ^(k-1) * ψ^2 = ø^(k-1) * (ø + 1) - ψ^(k-1) * (ψ + 1) |
Using the known values of ø and ψ, it is easy to verify that both ø^2 = ø + 1 and ψ^2 = ψ + 1. However, we can show this another way. Note that these are both expressions of the form x^2 = x + 1. Turning this into x^2 - x - 1 = 0, we can use the quadratic formula:
x = (1 +/- √(1 - 4(-1))) / 2 |
= (1 +/- √5) / 2 |
= ø or ψ |
Therefore, the equality Fib(k + 1) = Fib(k) + Fib(k - 1) holds, meaning that, given our inductive assumption, the value of Fib(k + 1) is correct. This method of computing Fibonacci numbers works.
TODO: Look this over between two and ten more times, and be more explicit