Mathematics for Computer Science

Chapter 15 Generating Functions636

We can use the quadratic formula to find the rootsr 1 ;r 2 of the denominator, 1
xx^2.

r 1 D

1

p

5

2

;r 2 D

1 C

p

5

2

:

So
1 xx^2 D.xr 1 /.xr 2 /Dr 1 r 2 .1x=r 1 /.1x=r 2 /:

With a little algebra, we find that

R.x/D

x

.1 ̨ 1 x/.1 ̨ 2 x/

where

̨ 1 D

1 C

p

5

2

̨ 2 D

1

p

5

2

:

Next we findc 1 andc 2 which satisfy:

x

.1 ̨ 1 x/.1 ̨ 2 x/

D

c 1

1  ̨ 1 x

C

c 2

1  ̨ 2 x

(15.11)

In general, we can do this by plugging in a couple of values forxto generate two
linear equations inc 1 andc 2 and then solve the equations forc 1 andc 2. A simpler
approach in this case comes from multiplying both sides of (15.11) by the left hand
denominator to get
xDc 1 .1 ̨ 2 x/Cc 2 .1 ̨ 1 x/:

Now lettingxD1= ̨ 2 we obtain

c 2 D

1= ̨ 2

1 ̨ 1 = ̨ 2

D

1

̨ 2 ̨ 1

D

1

p

5

;

and similarly, lettingxD1= ̨ 1 we obtain

c 1 D

1

p

5

:

Plugging these values forc 1 ;c 2 into equation (15.11) finally gives the partial frac-
tion expansion

R.x/D

x

1 xx^2

D

1

p

5



1

1  ̨ 1 x

1

1  ̨ 2 x