Wednesday, December 9, 2009

SICP Exercise 1.13: Fibonacci and the Golden ratio

From SICP section 1.2.2 Tree Recursion

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) / √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 proof

As 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 another

Let'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.

9 comments:

Mark Feeney said...

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

柯嘉 said...

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.

Iain said...

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.

waldo said...

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

Alexander Grebenyuk said...

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)

Фёдор Ананьев said...

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.

Bill the Lizard said...

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

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. :)

Brendan said...

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.

Brendan said...

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