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.

- Show that Fib(n) = (ɸ
- 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.