Fibonacci Numbers and Generating Functions - psholtz/MIT-SICP GitHub Wiki

This problem develops properties of the Fibonacci numbers, which are defined by recurrence. We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) F as:

a. Show that F(z) = z + zF(z) + z^2F(z).

b. Show that

where

and

c. Show that

d. Prove that F(i) = phi^i/sqrt(5), rounded to the nearest integer.

e. Prove that F(i+2) >= phi^i for i >= 0.

Solution

We first demonstrate that F(z) = z + zF(z) + z^2F(z) as follows.