Mathematics for Computer Science

15.3. Partial Fractions 637

Each term in the partial fractions expansion has a simple power series given by the
geometric sum formula:

1

1  ̨ 1 x

D 1 C ̨ 1 xC ̨ 12 x^2 C




1

1  ̨ 2 x

D 1 C ̨ 2 xC ̨ 22 x^2 C

Substituting in these series gives a power series for the generating function:

R.x/D

1

p

5

.1C ̨ 1 xC ̨^21 x^2 C


/.1C ̨ 2 xC ̨ 22 x^2 C


/

;

so

ŒxnçR.x/D

̨n 1  ̨n 2

p

5

D

1

p

5

1 C

p

5

2

!n

1

p

5

2

!n!

(15.12)

15.3.1 Partial Fractions with Repeated Roots

Lemma 15.3.1 generalizes to the case when the denominator polynomial has a re-
peated nonzero root with multiplicitymby expanding the quotient into a sum a
terms of the form c

.1 ̨x/k

where ̨is the reciprocal of the root andkm. A formula for the coefficients of
such a term follows from the donut formula (15.10).

Œxnç



c

.1 ̨x/k



Dc ̨n

nC.k1/

n

!

: (15.13)

When ̨D 1 , this follows from the donut formula (15.10) and termwise multipli-
cation by the constantc. The case for arbitrary ̨follows by substituting ̨xforx
in the power series; this changesxninto. ̨x/nand so has the effect of multiplying
the coefficient ofxnby ̨n.^2

(^2) In other words,
ŒxnçF. ̨x/D ̨n
ŒxnçF.x/: