Given:

Def 1.    ϕ = (1 + √5)/2

Def 2.    ψ = (1 - √5)/2

Def 3.    Fib(n) = Fib(n-1) + Fib(n-2)    for n > 1


To be proved:

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

Fib(n) = the closest integer to ϕ^n / √5 .


First, we prove

Eq 2.     ϕ^2 = ϕ + 1.

Taking the common definition of ϕ, as

    a   a + b
ϕ = - = -----
    b     a   ,

we see that

bϕ   bϕ + b
-- = ------                                     (by substitution of a = bϕ)
b      bϕ

    ϕ+1
ϕ = ---                                         (canceling b)
     ϕ

ϕ^2 = ϕ + 1                                     (multiplying by ϕ)


We may also prove Eq 2 by beginning with the definition of ϕ given in the text:

ϕ = (1 + √5)/2                                                    Def 1.

      (1 + √5)^2
ϕ^2 = ----------                                                  squaring both sides
         2^2

ϕ^2 = (6 + 2√5)/4 = (3 + √5)/2

ϕ^2 = (1 + √5)/2 + 1

ϕ^2 = ϕ+1                                                         Q.E.D.


Similarly, we may prove

Eq 3.     ψ^2 = ψ+1

as follows:

ψ = (1 - √5)/2                                                    Def 2.

ψ^2 = (6 - 2√5)/4 = (3 - √5)/2 = 1 + (1 - √5)/2 = 1 + ψ           squaring both sides and simplifying, as above


Next we prove that

Eq 4.     ϕ^n = ϕ^(n-1) + ϕ^(n-2)   for n > 1

by induction on n-1 and n-2, as follows:

  ϕ^2 = ϕ+1                                                       first base case, proved as Eq 2 above.

  ϕ^3 = ϕ(ϕ^2)                                                    by inspection
  ϕ^3 = ϕ(ϕ+1)                                                    by substitution from the first base case
  ϕ^3 = ϕ^2 + ϕ                                                   second base case

and for n > 3,

  ϕ^n = ϕ(ϕ^(n-1))

  ϕ^(n-1) = ϕ^(n-2) + ϕ^(n-3)                                     by inductive hypothesis

  ϕ^n = ϕ(ϕ^(n-2) + ϕ^(n-3))                                      by substitution

  ϕ^n = ϕ^(n-1) + ϕ^(n-2)                                         Q.E.D.

We may also prove

Eq 5.     ψ^n = ψ^(n-1) + ψ^(n-2)   for n > 1

analogously, beginning with Eq 3 proved above.



Now, we prove Eq 1 by induction as follows:

When n = 0,

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

When n = 1,

  (ϕ^n - ψ^n)/√5

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

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

   √5
= ---- = 1 = Fib(1).
   √5

When n > 1,

Fib(n) = Fib(n-1) + Fib(n-2)                                      Def 3

Fib(n-1) = (ϕ^(n-1) - ψ^(n-1))/√5                                 assumed by inductive hypothesis
Fib(n-2) = (ϕ^(n-2) - ψ^(n-2))/√5

         ϕ^(n-1) - ψ^(n-1) + ϕ^(n-2) - ψ^(n-2)
Fib(n) = -------------------------------------                    by substitution of inductive assumptions into the definition
                         √5

         ϕ^(n-1) + ϕ^(n-2) - ψ^(n-1) - ψ^(n-2)
Fib(n) = -------------------------------------                    re-arranging terms
                         √5

         ϕ^n - ψ^n
Fib(n) = ---------                                                by substitution of Eq 4 and Eq 5 proved above
             √5

Thus Eq 1 is proved.

We may clearly see that ψ, raised to 2 or any higher power, cannot be greater than 1/2, therefore

Fib(n) = the closest integer to ϕ^n / √5 .