Exercise 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}) / √5Some 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.

φ

1/φ + 1 = φ

^{2}= φ + 11/φ + 1 = φ

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

ψ

1/ψ + 1 = ψ

^{2}= ψ + 11/ψ + 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 proof

As the hint recommends, let's start by proving inductively that

Fib(n) = (φ

^{n}- ψ^{n}) / √5For 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

Fib(1) = 1

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

= 1 + 0

= 1

On the Right-hand side we have:

for n = 0

(φ

= (1 - 1) / √5

= 0 / √5

= 0

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

= 0 / √5

= 0

for n = 1

(φ

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

^{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

(φ

= ((φ + 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

^{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) = (φ

Fib(n-1) = (φ

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

^{n-1}- ψ^{n-1}) / √5does it follow that

Fib(n+1) = (φ

^{n+1}- ψ^{n+1}) / √5is 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}) / √5In the 10th step of the transformation above I used the following properties of φ and ψ to do substitutions:

1/φ + 1 = φ

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 another

Let's rearrange the equation just a bit before continuing on.

Fib(n) = (φ

Fib(n) = φ

Fib(n) - φ

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

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

^{n}/√5 = ψ^{n}/√5I 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/2or

ψ^{n}≤ √5/2Since ψ 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}≤ 1for all non-negative integer values of n.

We can also simply evaluate √5/2.

√5/2 = 1.118...

Since

ψ

and^{n}≤ 1√5/2 > 1

it's pretty clear that

ψ

^{n}≤ √5/2and 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.

## 10 comments:

Great solution. Your post helped me out a lot with this exercise. Thanks!

Very clear and acceptable! Thanks for sharing.

If we note that 1/φ + 1/φ/φ = 1 and 1/ψ + 1/ψ/ψ = 1, step 7, 8, 9, and 10 of the original 10-step proof can be omitted.

I feel a little cheated because I didn't know that

1/φ + 1 = φ

and the book didn't mention that property, only that

φ^2 = φ + 1

otherwise, good proof. I definitely need to learn more math, though.

I think the line (third under "One proof leads to another"): φ and ψ should be swapped?

...

Fib(n) - φn/√5 = ψn/√5 should be Fib(n) - ψn/√5 = φn/√5

Thank you for all the solutions. They are all really descriptive and helpful.

btw the transformation in inductive step would be much clearer if you do it this way:

fib(n+2) = fib(n+1) + fib(n)

fib(n) = fib(n+2) - fib(n+1)

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

φ^n - ψ^n = φ^(n+2) - ψ^(n+2) - φ^(n+1) + ψ^(n+1)

φ^n - ψ^n = φ^n * (φ^2 - φ^1) - ψ^n * (ψ^2 - ψ^1)

thank you yet again. I'd rather prove second part (difference is smaller that half-an-integer) with strict math, not with calculator. But jeez, that's a bit too much for programming enthusiast already.

Фёдор Ананьев,

You're welcome. Thanks for reading.

This was one of my favorite SICP exercises from the first chapter because it gave me a chance to dust off my algebra skills. :)

I made have identified a mistake, please check!

at this point:

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

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

The second line should be

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

and then you should continue with

|- ψ^n/√5| < 1/2 since the requirement is that it must round to Fib(n) from either above or below.

⇐ 0 < ψ^n/√5 < 1/2 ⟨ since it is >0⟩

⇐ 0 < ψ^n < √5/2

⇐ ((1 - √5)/2)^n < √5/2

(1 - √5)/2) is less than 1 so largest LHS exists with the smallest n (n=0)

⇐ 1 < √5/2

⇐ 1 < ~1.11, which is #t!

then prove ψ^n/√5 < 1/2 (You used ≤ which seems incorrect when thinking of what "closest integer to..." means)

Interestly, I think you might have been able to procede yourway since the approximated Fib(n) is always above the actual Fib(n) so it gets rounded down, which makes sense since the only difference between the approximation and precise function is that the approx. Fix is lacking "- φ^n/√5", a negative value.

(Oops, ignore the duplicate crap, I forgot to delete it whilst rewriting the post)

Not sure if I understand correctly, but in the fib(n+1) proof portion, 5th line down where you go from:

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

to:

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

Couldn't you also just say that: φ^(n+1) = φ^n + φ^(n-1), since φ^2 = φ +1, and then just skip right to (φ^n+1 - ψ^n+1)/√5?

Not trying to be clever or anything, that's just how I did it and I want to make sure I didn't miss anything. Thanks so much for posting these.

Post a Comment