.

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:

  1. Using induction, show that Fib(n) = (ɸn - ψn)/√5.
    1. Show that Fib(n) = (ɸn - ψn)/√5 when n = 0.
    2. how that Fib(n) = (ɸn - ψn)/√5 when n = 1.
    3. 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.
    4. Conclude that Fib(n) = (ɸn - ψn)/√5 for any n ≥ 0.
  2. Use 1. to show that Fib(n) is the closest integer to ɸn/√5.
    1. Show that the absolute value of 1/√5 is less than 1/2.
    2. Show that the absolute value of ψ is less than 1.
    3. Conclude that the absolute value of ψn/√5 is less than 1/2.
    4. 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

big fraction of phi - psi written out in numbers, all divided by sqrt 5

((2sqrt5)/2)/sqrt5

= 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:

the assumptions written out

multiply the top half of the first fraction by ɸ + ψ, which = 1:

after multiplying the top half of the first fraction by ɸ + ψ

replace one ɸ * ψ with -1 in each of the two middle terms of the top half of the first fraction, since ɸ * ψ = -1:

after replacing ɸψ with -1 in terms 2 and 3

combine the two fractions and cancel some terms:

(phi ^ n - psi n)/ sqrt 5

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.