Exercise 1.13. Prove that Fib(n) is the closest integer to ɸn/√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) = (ɸn - ψn)/√5.
Outline of the proof, following the hint:
- Using induction, show that Fib(n) = (ɸn - ψn)/√5.
- Show that Fib(n) = (ɸn - ψn)/√5 when n = 0.
- how that Fib(n) = (ɸn - ψn)/√5 when n = 1.
- Show that for any n ≥ 2, if Fib(n-1) = (ɸn-1 - ψn-1)/√5 and Fib(n-2) = (ɸn-2 - ψn-2)/√5, then Fib(n) = (ɸn - ψn)/√5.
- Conclude that Fib(n) = (ɸn - ψn)/√5 for any n ≥ 0.
- Use 1. to show that Fib(n) is the closest integer to ɸn/√5.
- Show that the absolute value of 1/√5 is less than 1/2.
- Show that the absolute value of ψ is less than 1.
- Conclude that the absolute value of ψn/√5 is less than 1/2.
- Conclude that the closest integer to Fib(n) + ψn/√5, which is ɸn/√5, as shown in 1., must be Fib(n).
1. Show that Fib(n) = (ɸn - ψn)/√5.
a. Show that Fib(n) = (ɸn - ψn)/√5 when n = 0.
When n = 0,
(ɸn - ψn)/√5
= (ɸ0 - ψ0)/√5
= (1 - 1)/√5
= 0
= Fib(0).
b. Show that Fib(n) = (ɸn - ψn)/√5 when n = 1.
When n = 1,
(ɸn - ψn)/√5
= (ɸ - ψ)/√5
= 1
= Fib(1).
c. Show that for any n ≥ 2, if Fib(n-1) = (ɸn-1 - ψn-1)/√5 and Fib(n-2) = (ɸn-2 - ψn-2)/√5, then Fib(n) = (ɸn - ψn)/√5.
Assume that n ≥ 2, Fib(n-1) = (ɸn-1 - ψn-1)/√5, and Fib(n-2) = (ɸn-2 - ψn-2)/√5.
First, note that ɸ * ψ = -1 and ɸ + ψ = 1. We’ll use these later.
Fib(n)
from the definition of the Fib numbers:
= Fib(n-1) + Fib(n-2)
from the assumptions above:
multiply the top half of the first fraction by ɸ + ψ, which = 1:
replace one ɸ * ψ with -1 in each of the two middle terms of the top half of the first fraction, since ɸ * ψ = -1:
combine the two fractions and cancel some terms:
So Fib(n) = (ɸn - ψn)/√5.
d. Conclude that Fib(n) = (ɸn - ψn)/√5 for any n ≥ 0.
If the positive integer is 0 or 1, we’ve already seen that Fib(n) = (ɸn - ψn)/√5 is true. If the positive integer is 2, we can use the fact that for any n ≥ 2, if Fib(n) = (ɸn - ψn)/√5 is true for n - 1 and n - 2, then it’s true for n, because it’s true for 0 and 1. Once we know it’s true for n = 2, can do the same to show that it’s true for n = 3. We can continue doing that until we got to any particular positive number.
2. Use 1. to show that Fib(n) is the closest integer to ɸn/√5.
a. Show that the absolute value of 1/√5 is less than 1/2.
1/√5 is around 0.4472, which has absolute value less than 1/2.
b. Show that the absolute value of ψ is less than 1.
ψ, which is (1 - √5)/2, is around -0.6180, which has absolute value less than one.
c. Conclude that the absolute value of ψn/√5 is less than 1/2.
For positive integers n, we get to ψn/√5 by multiplying 1/√5 by ψ, n times. If we start with something with absolute value less than 1/2 and multiply it n times by something with absolute value less than 1, the result will still have absolute value less than 1/2.
d. Conclude that the closest integer to Fib(n) + ψn/√5, which is ɸn/√5, as shown in 1., must be Fib(n).
We know that Fib(n) is an integer, since Fib numbers are made by adding integers. And from 1., we know that Fib(n) = (ɸn - ψn)/√5, which is the same as ɸn/√5 - ψn/√5. Since the second part of that has absolute value less than 1/2, Fib(n) must be the closest integer to the first part of it, which is ɸn/√5.