SICP Exercise 1.13: Fibonacci Numbers

Prove that Fib(n) is the closest integer to ϕⁿ/√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) = (ϕⁿ - ψⁿ)/√5.

The definition of Fib(n) given in section 1.2.2 is:

Fib(n) =	0	if n = 0
	1	if n = 1
	Fib(n - 1) + Fib(n - 2)	otherwise

Abelson & Sussman have given us a hint here. They suggest proving that Fib(n) = (ϕⁿ - ψⁿ)/√5. Let's start with proving that and then move on to figuring out why the hint is correct.

First, let's prove the base cases of n = 0 and n = 1. When n = 0:

  (ϕ0 - ψ0)/√5
= (1 - 1)/√5
= 0/√5
= 0
= Fib(0)

and when n = 1:

  (ϕ1 - ψ1)/√5
= (((1 + √5)/2)1 - ((1 - √5)/2)1)/√5
= ((1 + √5)/2 - (1 - √5)/2)/√5
= ((1 + √5 - 1 + √5)/2)/√5
= 2√5/2/√5
= √5/√5
= 1
= Fib(1)

To then prove by induction that their hint holds for all n we then first make the assumptions that the following two formulae hold:

  Fib(n - 1) = (ϕn-1 - ψn-1)/√5
  Fib(n)     = (ϕn - ψn)/√5

Next we try to prove that, given these assumptions, the formula also holds for n + 1. I.e. we need to prove that Fib(n + 1) = (ϕⁿ⁺¹ - ψⁿ⁺¹)/√5. Before we do this, a little side track... We already know that ϕ² = ϕ + 1. We can also prove the corresponding equation of ψ² = ψ + 1:

  ψ2
= ((1 - √5)/2)2
= (1 - √5)/2)(1 - √5)/2)
= (1 - √5)(1 - √5)/4
= (1 - 2√5 + 5)/4
= (6 - 2√5)/4
= (3 - √5)/2
= (1 - √5)/2 + 1
= ψ + 1

Okay, having done that, back to our proof for n + 1:

  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-1) - (ψn + ψn-1))/√5
= ((ϕ + 1)ϕn-1 - (ψ + 1)ψn-1)/√5
= (ϕ2ϕn-1 - ψ2ψn-1)/√5
= (ϕn+1 - ψn+1)/√5

So we've proved by induction that Fib(n) = (ϕⁿ - ψⁿ)/√5. But why does that prove that Fib(n) is the closest integer to ϕⁿ/√5?

Well if Fib(n) is the closest integer to ϕⁿ/√5 then ϕⁿ/√5 must be within 1/2 of Fib(n). In other words, we need to prove that:

|(Fib(n) - ϕn/√5)| ≤ 1/2

Recall that we've already shown that Fib(n) = (ϕⁿ - ψⁿ)/√5, so we can proceed as follows:

  |(Fib(n) - ϕn/√5)| ≤ 1/2
⇒ |((ϕn - ψn)/√5 - ϕn/√5)| ≤ 1/2
⇒ |(-ψn/√5)| ≤ 1/2
⇒ |ψn/√5| ≤ 1/2
⇒ |ψn| ≤ √5/2

So we just need to to prove that |ψⁿ| ≤ √5/2:

• We know that, for any value of x such that -1 ≤ x ≤ 1 and any value of n ≥ 1, it's the case that 0 ≤ |(xⁿ)| ≤ 1
• ψ = (1 - √5)/2 ≈ -0.6180, so 0 ≤ |ψⁿ| ≤ 1
• √5/2 ≈ 1.1180

So |ψⁿ| ≤ √5/2, and so Fib(n) produces the closest integer to ϕⁿ/√5