From SICP section

1.2.2 Tree RecursionExercise 1.13 asks us to prove that Fib(n) is the closest integer to φ

^{n}/√5, where

φ = (1 + √5)/2.

The exercise also gives us the following hint:

Let ψ = (1 - √5)/2. Use induction and the definition of Fibonacci numbers to prove that

Fib(n) = (φ^{n} - ψ^{n}) / √5

Some may recognize that this question is closely related to the

closed form expression for Fibonacci numbers, also known as

Binet's formula.

You may also recognize the quantity (1 + √5)/2, denoted by the Greek letter φ (phi), as the

Golden ratio.

This mathematical constant has many interesting properties, a couple of which will be useful in our proof.

φ^{2} = φ + 1

1/φ + 1 = φ

The second constant introduced in the hint (1 - √5)/2, denoted by the Greek letter ψ (psi), shares the same properties.

ψ^{2} = ψ + 1

1/ψ + 1 = ψ

Before tackling the problem, let's take a look at the sequences in question to try and get a feel for what we're trying to prove. It's safe to assume that everyone is familiar with the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the preceding two.

We can use the following procedures to quantify φ

^{n}/√5 for several values of n.

`(define phi`

(/ (+ 1 (sqrt 5)) 2))

(define (^ base exponent)

(define (*^ exponent acc)

(if (= exponent 0)

acc

(*^ (- exponent 1) (* acc base))))

(*^ exponent 1))

(define (f n)

(/ (^ phi n) (sqrt 5)))

The following output shows that this function does track closely with the Fibonacci sequence.

`> (f 0)`

0.4472135954999579

> (f 1)

0.7236067977499789

> (f 2)

1.1708203932499368

> (f 3)

1.8944271909999157

> (f 4)

3.0652475842498528

> (f 5)

4.959674775249769

> (f 6)

8.024922359499621

> (f 7)

12.984597134749391

> (f 8)

21.009519494249012

Each term is within 1/2 of the corresponding term of Fib(n), which is what we're asked to prove. This is only a small amount of empirical evidence, though, which is a far cry from proof. It does show that what we're asked to prove is at least reasonable, though. (It's always a good idea to show that an assertion is at least

reasonable before you go about trying to

prove it.)

The inductive proofAs the hint recommends, let's start by proving inductively that

Fib(n) = (φ^{n} - ψ^{n}) / √5

For the base cases we'll show that the left-hand side of the equation above is equal to the right-hand side for n = 0, n = 1, and n = 2.

On the Left-hand side we have:

Fib(0) = 0

Fib(1) = 1

Fib(2) = Fib(1) + Fib(0)

= 1 + 0

= 1

On the Right-hand side we have:

for n = 0

(φ^{n} - ψ^{n}) / √5 = (φ^{0} - ψ^{0}) / √5

= (1 - 1) / √5

= 0 / √5

= 0

for n = 1

(φ^{n} - ψ^{n}) / √5 = (φ^{1} - ψ^{1}) / √5

= ((1 + √5)/2) - ((1 - √5)/2) / √5

= (1/2 + √5/2) - (1/2 - √5/2) / √5

= (1/2 + √5/2 - 1/2 + √5/2) / √5

= (√5/2 + √5/2) / √5

= (2 * √5/2) / √5

= √5 / √5

= 1

for n = 2

(φ^{n} - ψ^{n}) / √5 = (φ^{2} - ψ^{2}) / √5

= ((φ + 1) - (ψ + 1)) / √5

= (((1 + √5)/2 + 1) - ((1 - √5)/2 + 1)) / √5

= ((1 + √5)/2 + 1 - (1 - √5)/2 - 1) / √5

= ((1 + √5)/2 - (1 - √5)/2) / √5

= ((1 + √5) - (1 - √5)) / 2 / √5

= (1 + √5 - 1 + √5) / 2 / √5

= (√5 + √5) / 2 / √5

= (2 * √5) / 2 / √5

= √5 / √5

= 1

So far, so good. Now for the inductive step. If we assume that both of the following are true:

Fib(n) = (φ^{n} - ψ^{n}) / √5

Fib(n-1) = (φ^{n-1} - ψ^{n-1}) / √5

does it follow that

Fib(n+1) = (φ^{n+1} - ψ^{n+1}) / √5

is true also? Let's find out!

We'll start from the defining recurrence relation of the Fibonacci sequence and see if the two assumptions above can lead us to the correct conclusion. Remember that we also have the properties of φ and ψ that were introduced at the beginning at our disposal.

Fib(n+1) = Fib(n) + Fib(n-1)

= (φ^{n} - ψ^{n}) / √5 + (φ^{n-1} - ψ^{n-1}) / √5

= ((φ^{n} - ψ^{n}) + (φ^{n-1} - ψ^{n-1})) / √5

= (φ^{n} - ψ^{n} + φ^{n-1} - ψ^{n-1}) / √5

= (φ^{n} + φ^{n-1} - ψ^{n} - ψ^{n-1}) / √5

= ((φ^{n} + φ^{n-1}) - (ψ^{n} + ψ^{n-1})) / √5

= (φ^{n+1} * (φ^{-1} + φ^{-2}) - ψ^{n+1} * (ψ^{-1} + ψ^{-2})) / √5

= (φ^{n+1} * φ^{-1} * (1 + φ^{-1}) - ψ^{n+1} * ψ^{-1} * (1 + ψ^{-1})) / √5

= (φ^{n+1} * 1/φ * (1 + 1/φ) - ψ^{n+1} * 1/ψ * (1 + 1/ψ)) / √5

= (φ^{n+1} * 1/φ * (φ) - ψ^{n+1} * 1/ψ * (ψ)) / √5

= (φ^{n+1} - ψ^{n+1}) / √5

In the 10th step of the transformation above I used the following properties of φ and ψ to do substitutions:

1/φ + 1 = φ

1/ψ + 1 = ψ

This concludes the inductive proof from the hint, but where does that leave us? How does that help us prove that Fib(n) is the closest integer to φ

^{n}/√5?

One proof leads to anotherLet's rearrange the equation just a bit before continuing on.

Fib(n) = (φ^{n} - ψ^{n}) / √5

Fib(n) = φ^{n}/√5 - ψ^{n}/√5

Fib(n) - φ^{n}/√5 = ψ^{n}/√5

I did this bit of manipulation because we're trying to prove something about the relationship between Fib(n) and φ

^{n}/√5. Specifically, we're trying to prove that the

difference between them is always less than 1/2. In its current form, all that we have left to prove is that

ψ

^{n}/√5 ≤ 1/2

or

ψ

^{n} ≤ √5/2

Since ψ is defined to be (1 - √5)/2, we can simply evaluate it to find that

ψ = -0.618304...

Since the n in Fib(n) is always going to be an integer and

n ≥ 0

will always be true, and

ψ < 1

we know that

ψ^{n} ≤ 1

for all non-negative integer values of n.

We can also simply evaluate √5/2.

√5/2 = 1.118...

Since

ψ^{n} ≤ 1

and

√5/2 > 1

it's pretty clear that

ψ^{n} ≤ √5/2

and therefore

Fib(n) is the closest integer to φ^{n}/√5.

QED

Related:For links to all of the SICP lecture notes and exercises that I've done so far, see

The SICP Challenge.