Mathematics for Computer Science

15.5. Formal Power Series 643

used above to derive generating functions for the Fibonacci and Tower of Hanoi

examples carries over to yield a quotient of polynomials that defines the generating

functionf.0/Cf.1/xCf.2/x^2 C


. Then partial fractions can be used to find

a formula forf.n/that is a linear combination of terms of the formnk ̨nwherek

is a nonnegative integerdand ̨is the reciprocal of a root of the denominator

polynomial. For example, see Problems 15.15, 15.16, 15.20, and 15.21.

15.5 Formal Power Series

15.5.1 Divergent Generating Functions

LetF.x/be the generating function fornŠ, that is,

F.x/WWD 1 C1xC2x^2 C


CnŠxnC


:

Becausexn D o.nŠ/for allx ¤ 0 , this generating function converges only at

xD 0.^3

Next, letH.x/be the generating function forn
nŠ, that is,

H.x/WWD 0 C1xC4x^2 C


Cn
nŠxnC


:

Again,H.x/converges only forxD 0 , soH.x/andF.x/describe the same,

trivial, partial function on the reals.

On the other hand,F.x/andH.x/have different coefficients for all powers of

xgreater than 1, and we can usefully distinguish them as formal, symbolic objects.

To illustrate this, note than by subtracting 1 fromF.x/and then dividing each

of the remaining terms byx, we get a series where the coefficient ifxnis.nC1/Š.

That is

Œxnç



F.x/ 1

x



D.nC1/Š: (15.16)

Now a little further formal reasoning aboutF.x/andH.x/will allow us to

deduce the following identity fornŠ:^4

nŠD 1 C

Xn

iD 1

.i1/
.i1/Š (15.17)

(^3) This section is based on an example from “Use of everywhere divergent generating function,”
mathoverflow, response 8,147 by Aaron Meyerowitz, Nov. 12, 2010.
(^4) A combinatorial proof of (15.17) is given in Problem 14.64