Mathematics for Computer Science

Chapter 15 Generating Functions638

15.4 Solving Linear Recurrences

15.4.1 A Generating Function for the Fibonacci Numbers

The Fibonacci numbersf 0 ;f 1 ;:::;fn;:::are defined recursively as follows:

f 0 WWD 0

f 1 WWD 1

fnDWWDfn 1 Cfn 2 (forn 2 ):

Generating functions will now allow us to derive an astonishing closed formula for

fn.

LetF.x/be the generating function for the sequence of Fibonacci numbers, that

is,

F.x/WWDf 0 Cf 1 xCf 2 x^2 C


fnxnC


:

Reasoning as we did at the start of this chapter to derive the formula for a geometric

series, we have

F.x/ D f 0 C f 1 x C f 2 x^2 C 


 C fnxnC


:

xF.x/ D  f 0 x  f 1 x^2  


  fn 1 xnC


:

x^2 F.x/ D  f 0 x^2  


  fn 2 xnC


:

F.x/.1xx^2 / D f 0 C .f 1 f 0 /x C 0x^2 C 


 C 0xnC


:

D 0 C 1x C 0x^2 D x;

so

F.x/D

x

1 xx^2

:

ButF.x/is the same as the function we used to illustrate the partial fraction method

for finding coefficients in Section 15.3. So by equation (15.12), we arrive at what

is calledBinet’s formula:

fnD

1

p

5

1 C

p

5

2

!n

1

p

5

2

!n!

(15.14)

Binet’s formula for Fibonacci numbers is astonishing and maybe scary. It’s not

even obvious that the expression on the right hand side (15.14) is an integer. But

the formula is very useful. For example, it provides—via the repeated squaring

method—a much more efficient way to compute Fibonacci numbers than crunch-

ing through the recurrence. It also make explicit the exponential growth of these

numbers.