7. Formal Power Series.

In Sections 4 through 6 we have been manipulating infinite power series in

one or more indeterminates without concerning ourselves that such manipulations
are justified. So far we have not run into any problems, but perhaps that was just
a matter of good luck. In this section we will see which algebraic manipulations
are valid for formal power series (and more generally for formal Laurent series),
as well as seeing some manipulations which are invalid. Special attention should
be paid to the concept of convergence of a sequence of formal power series. Many
students consistently confuse this with the concept of convergence of a sequence
of real numbers (familiar from calculus), but the two concepts are in fact quite
different.
First we recall some basic concepts and terminology of abstract algebra. (These
are covered in MATH 135, but some review is warranted.) A ring is a set R which
has two special elements, a zero 0 ∈ R and a one 1 ∈ R, and is equipped with two
binary operations, multiplication · : R×R → R and addition + : R×R → R. A long
list of axioms completes the definition, but suffice it here to say that the axioms state
that the usual rules of integer arithmetic hold for (R; ·, +; 0, 1) with one exception.
In general, the multiplication in a ring is not required to be commutative: that is,
the rule ab = ba for all a, b ∈ R is not in general required. When multiplication
in R is commutative we say that R is a commutative ring. (The ring of 2–by–2
matrices with real entries is an example of a ring that is not commutative.) Some
noncommutative rings are in fact useful in combinatorial enumeration, but all of the
rings of importance in these notes are commutative.
The point of the previous paragraph is that when we say “R is a commutative
ring” we mean that the familiar rules of arithmetic continue to hold for R.
Let (R; ·, +; 0, 1) be a commutative ring. An element a ∈ R is a zero–divisor
if a 6= 0 and there is an element b ∈ R with b 6= 0 such that ab = 0. For example, in
the ring Z15 of integers modulo 15, we have [3][5] = [15] = [0], so that [3] and [5] are
zero–divisors in Z15 . If R has no zero–divisors then R is called an integral domain.
An element a ∈ R is invertible if there is an element b ∈ R such that ab = 1. Such
an element is unique if it exists, for if ac = 1 as well, then
b = b1 = b(ac) = (ba)c = (ab)c = 1c = c.
Here we have used several of the axioms, including associativity and commutativity
of multiplication. If a ∈ R is invertible, then the unique element b ∈ R such that
ab = 1 is denoted by a−1 , and is called the multiplicative inverse of a. Notice that
(a−1 )−1 = a. Finally, a commutative ring R is called a field if every a ∈ R with
a 6= 0 is invertible.
Proposition 7.1. Let R be a commutative ring. If R is a field then R is an integral
domain.
Proof. Arguing for a contradiction, suppose not – thus, assume that R is a field but
that a ∈ R is a zero–divisor. Then a 6= 0 so that a−1 exists, and there is a 0 6= b ∈ R
such that ab = 0. Now we calculate that
b = b1 = b(aa−1 ) = (ba)a−1 = (ab)a−1 = 0a−1 = 0,
which is the desired contradiction. 
There are several ways to construct a new ring starting from a ring which is
already known. We will just give the four constructions which are useful for our
purposes, and only for commutative rings. So, for the next little while, let R be a
commutative ring.
Definition 7.2 (The Polynomial Ring). The ring of polynomials in x with coeffi-
cients in R is denoted by R[x], and is defined as follows. Here x is an indeterminate,
meaning a symbol which is not in the set R, and is not a solution of any algebraic
equation with coefficients in R. The elements of R[x] are expressions of the form
f (x) = a0 + a1 x + a2 x2 + · · · + an xn
for some n ∈ N, in which ai ∈ R for all 0 ≤ i ≤ n. Addition and multiplication are
defined as you would expect, using the definitions of addition and multiplication in
R for the coefficients, the distributive and associative laws, and the exponent rule
for x – that is, xi · xj = xi+j . Since R is commutative, R[x] is also commutative,
but R[x] is never a field. The invertible elements of R[x] are just the constant
polynomials a0 with a0 invertible in R. In particular, x ∈ R[x] is not invertible. If
R is an integral domain then so is R[x] (this is Exercise 7.2(a)).
Definition 7.3 (The Ring of Rational Functions). The ring of rational functions
in x with coefficients in R is denoted by R(x), and is defined as follows. There
is some subtlety if R contains zero–divisors, so we will only consider the case in
which R is an integral domain. The elements of R(x) are of the form f (x)/g(x)
with f (x), g(x) ∈ R[x] and g(x) 6= 0. Addition and multiplication are bootstrapped
up from R[x] by using the familiar means of manipulating fractions, and R(x) is
commutative because R is. Every nonzero element f (x)/g(x) has a multiplicative
inverse g(x)/f (x), so that R(x) is a field. In the expression f (x)/g(x) we may take
g(x) = 1, which shows that R[x] is a subset of R(x). The algebraic operations of
these two rings agree on this subset R[x], as is easily verified.
Definition 7.4 (The Ring of Formal Power Series). The ring of formal power
series in x with coefficients in R is denoted by R[[x]], and is defined as follows. The
elements of R[[x]] are infinite expressions of the form
f (x) = a0 + a1 x + a2 x2 + · · · + an xn + · · ·
in which an ∈ R for all n ∈ N. Addition and multiplication are defined just as for
the ring of polynomials R[x], and R[[x]] is commutative because R is. It is clear
that R[x] is a subset of R[[x]], and that the algebraic operations of these two rings
agree on this subset. The ring R[[x]] is not a field because, for example, x is not
invertible in R[[x]]. However, as the following proposition shows, there are quite a
few invertible elements in R[[x]].
P∞ i
Proposition 7.5. Let R be a commutative ring, and let f (x) = i=0 ai x be a
formal power series in R[[x]]. Then f (x) is invertible in R[[x]] if and only if a0 is
invertible in R.
Proof. We
P∞need to determine whether or not there exists a formal power series
j
g(x) = j=0 bj x in R[[x]] such that f (x)g(x) = 1. Expanding the product, we
have
∞
! ∞ !
X X
f (x)g(x) = ai xi bj x j
i=0 j=0
∞ X
∞ ∞ k
!
X X X
= ai bj xi+j = ai bk−i xk .
i=0 j=0 k=0 i=0

Comparing the coefficient of xk on both sides of f (x)g(x) = 1, we see that g(x)

satisfies the equation if and only if a0 b0 = 1 and ki=0 ai bk−i = 0 for all k ≥ 1. If a0
P
is not invertible in R then the equation a0 b0 = 1 can not be solved for b0 , so that
g(x) does not exist and f (x) is not invertible in R[[x]]. If a0 is invertible in R then
b0 := a−1
0 P exists. Each of the remaining equations (for k ≥ 1) can be rewritten as
a0 bk = − ki=1 ai bk−i , or, upon multiplying by b0 ,
k
X
bk = −b0 ai bk−i .
i=1

These equations can be solved by induction on k ≥ 1, yielding a solution for g(x)

which gives the multiplicative inverse of f (x). Therefore, f (x) is invertible in R[[x]].

Definition 7.6 (The Ring of Formal Laurent Series). The ring of formal Laurent
series in x with coefficients in R is denoted by R((x)), and is defined as follows.
The elements of R((x)) are infinite expressions of the form
f (x) = ar xr + ar+1 xr+1 + ar+2 xr+2 + · · ·
in which r ∈ Z and an ∈ R for all n ≥ r. That is, a formal Laurent series is a
generalization of a formal power series in which finitely many negative exponents
are permitted. Addition and multiplication are defined just as for the ring R[[x]] of
formal power series, and R((x)) is commutative because R is. (I encourage you to
check that when multiplying two formal Laurent series the coefficients of the product
really are polynomial functions of the coefficients of the factors, and hence are in
the ring R. This ensures that the multiplication in R((x)) is well–defined.) Note
that the ring R[[x]] is a subset of the ring R((x)), and that the algebraic operations
of these rings agree on the subset R[[x]]. If f (x) ∈ R((x)) and f (x) 6= 0, then there
is a smallest integer n such that [xn ]f (x) 6= 0; this is called the index of f (x) and
is denoted by I(f ). By convention, the index of 0 is I(0) := +∞. Concerning the
existence of multiplicative inverses in R((x)), we have the following proposition.
Proposition 7.7. Let R be a commutative ring. If R is a field then R((x)) is a
field.
P∞ n
Proof. Consider a nonzero f (x) = n=I(f ) an x in R((x)). Then aI(f ) 6= 0 so
that it Pis invertible in R, since R is a field. We may write f (x) = xI(f ) g(x) with
g(x) = ∞ n
n=0 an+I(f ) x , so that g(x) is a formal power series in R[[x]]. The coefficient
of x0 in g(x) is aI(f ) and, by Proposition 7.5, it follows that g(x) is invertible in R[[x]],
and hence in R((x)). Let h(x) := x−I(f ) g −1 (x). Then
f (x)h(x) = xI(f ) g(x)x−I(f ) g −1 (x) = 1,
so that h(x) = f −1 (x) and f (x) is invertible in R((x)). Therefore, R((x)) is a
field. 
The inclusions R[x] ⊂ R[[x]] ⊂ R((x)) and R[x] ⊂ R(x) have been remarked
upon already. In fact, if R is a field then R(x) ⊂ R((x)) as well. Also, the rings
R[[x]] and R(x) have a nontrivial intersection, but neither one contains the other.
Since we have no pressing need for these facts we will not pause to prove them, but
instead relegate them to Exercise 7.2.
The constructions above may be combined and iterated, since the commutative
ring R was quite general. For example, R[x, y, z] denotes the ring of polynomials
in three indeterminates x, y, and z. Similarly, R[y][[x]] denotes the ring of formal
power series in the indeterminate x with coefficients which are polynomials in the
indeterminate y.
Example 7.8
(The Binomial Series). In the polynomial ring Q[y], we define the
polynomials ny for every n ∈ N by
 
y y(y − 1) · · · (y − n + 1)
:= .
n n!
The binomial series is then defined in Q[y][[x]] to be
∞  
y
X y n
(1 + x) := x .
n=0
n
Notice that in the ring Q[y, z][[x]] we have the following identity:
∞  
y+z
X y+z n
(1 + x) = x
n=0
n
∞ X n   
X y z
= xn
n=0 j=0
j n−j
∞  
! ∞  
!
X y j X z k
= x x
j=0
j k=0
k
= (1 + x)y · (1 + x)z .
In this calculation we have used the Vandermonde Convolution Formula (Exercise
3.5). Notice that y and z, as well as x, are also indeterminates. Any complex
number α ∈ C may be substituted for y in (1 + x)y , and the resulting (1 + x)α is a
formal power series in C[[x]].
The usual rules of arithmetic hold for all of the rings constructed above, but
there are other operations on these rings that have no analogues in Z. Care must be
taken with these operations to ensure that they produce well–defined power series.
In other words, these operations are not universally defined.
The first of the new operations are formal differentiation and formal integra-
tion. Since R((x)) contains all the other rings above (if R is a P field) we will just
define these operations on a typical formal Laurent series f (x) = ∞ n
n=I(f ) an x . The
formal derivative is always defined as
∞
0 d X
f (x) := f (x) := nan xn−1 .
dx
n=I(f )

The formal integral is defined only if Q ⊆ R and a−1 = 0, in which case

xn+1
Z X
f (x)dx := an .
n+1
n≥I(f ), n6=−1

In particular, the formal integral is defined on all of R[[x]] when Q ⊆ R. One

can show algebraically from the definitions that the familiar rules of calculus (the
Product Rule, Quotient Rule, Chain Rule, Integration by Parts, and so on) continue
to hold when all the integrals involved are defined.
Example 7.9 (The Logarithmic and Exponential Series). (a) From calculus, we
know that as functions of a real variable t,
d 1
log(t) = .
dt t
Now let x := 1 − t, so that dx = −dt. Then
 
d 1 d 1 1
log = log(t) = = .
dx 1−x dt t 1−x
Assuming that log(1 − x)−1 = ∞ n
P
n=I cn x has a Laurent series expansion, we obtain
the equation
X∞ X∞
n−1
ncn x = xk .
n=I k=0
This implies that cn = 1/n for all n ≥ 1, and that cn = 0 for all n ≤ −1, but gives
no information about c0 . However, substituting x = 0 we see that c0 = log(1) = 0.
In summary, we have the expansion
∞
xn
  X
1
log = .
1−x n=1
n
(b) As another example, the defining properties of the exponential function
exp(x) are that exp(0) P= 1 and exp0 (x) = exp(x). Expanding this as a formal
Laurent series exp(x) = ∞ n
n=I an x we get the equation
∞ ∞
d X
n−1
X
exp(x) = nan x = am xm = exp(x).
dx n=I m=I

Comparing the coefficients of xn−1 we see that nan = an−1 for all n ≥ I. By
induction, this implies that an = 0 for all I ≤ n < 0, so that in fact I ≥ 0. From
exp(0) = 1 we see that a0 = 1, and it then follows that an = 1/n! for all n ∈ N, so
that ∞
X xn
exp(x) = .
n=0
n!

The Chain Rule for differentiation involves “composition” of formal Laurent

series, which has not yet been defined (and is not universally defined). In order to
discuss the operation of composition we must introduce the concept of convergence
of a sequence of formal Laurent series. This must not be confused with the concept
of convergence of the single series f (x) ∈ R((x)) if x is assigned a particular real
value! In our applications the case of formal power series is most important, and we
will restrict attention to this case for some points.
Definition 7.10 (Convergence of a Sequence of Formal Laurent Series). Let f1 (x),
f2 (x), f3 (x),. . . be a sequence of formal Laurent series in R((x)). This sequence is
convergent in R((x)) provided that the following two conditions hold:
• there is an integer J such that J ≤ I(fk ) for all k ∈ N, and
• for every n ∈ N there exists a Kn ∈ N and An ∈ R such that if k ≥ Kn then
[xn ]fk (x) = An .
The first condition says that there is a uniform lower bound for the indices of all of
the entries fk (x) of the sequence. The second condition says that if we focus atten-
tion on only the n–th power of x, and consider the sequence [xn ]fk (x) of coefficients
of xn in fk (x) as k → ∞, then this sequence (of elements of R) is eventally constant,
with the ultimate value An .
If (f1 (x), f2 (x), f3 (x), . . .) is a convergent sequence of formal Laurent series
then, with the above notations,
∞
X
f (x) := An x n
n=J
is a well–defined formal Laurent series, called the limit of the convergent sequence.
We use the notation
lim fk (x) = f (x)
k→∞
to denote this relationship.
Example 7.11. Here are a few simple examples for which you can check the
definition easily.
(a) lim xk = 0.
k→∞

(b) lim x−k does not exist.

k→∞
1
(c) lim (1 + x + · · · + xk ) = .
k→∞ 1−x
1
(d) lim does not exist.
k→∞ 1 − x/k

This last example is particularly instructive. You might think that the limit should
exist and equal 1. However, the coefficient of x1 in (1 − x/k)−1 is 1/k, and we see
that the sequence (1/k : k ≥ 1) is not eventually constant. Therefore, this sequence
of formal power series does not converge according to Definition 7.10.
Two important special cases of this concept of limits are the interpretations of
infinite sums and infinite products of formal Laurent series. For an infinite sequence
(fk (x) : k ∈ N) of formal Laurent series, we define
∞
X K
X
fk (x) := lim fk (x)
K→∞
k=0 k=0
and
∞
Y K
Y
fk (x) := lim fk (x),
K→∞
k=0 k=0
provided that these limits exist.
Example 7.12. Consider the infinite summation
∞
X xk
.
k=1
1 − xk
Does this converge? To check the definition, for each K ∈ N consider the partial
sum
K K
X xk X
xk + x2k + x3k + · · · .


fK (x) := k
=
k=1
1−x k=1
To show that limK→∞ fK (x) exists, we fix an n ∈ N and consider the sequence
[xn ]fK (x) as K → ∞. Is this sequence eventually constant? Yes it is! If K > n
then
K n
n n
X xk n
X xk
[x ]fK (x) = [x ] k
= [x ] k
= [xn ]fn (x)
k=1
1 − x k=1
1 − x
since the terms with k > n can only contribute to the coefficients of powers of x
which are strictly greater than n. Since this number [xn ]fn (x) depends only on n
and not on K, the sequence [xn ]fK (x) is eventually constant as K → ∞. Therefore,
the infinite summation converges. In fact,
∞ ∞
X xk X
k
= d(n)xn
k=1
1 − x n=1

in which d(n) is the number of positive integers that divide n.

Example 7.13. Consider the infinite product
∞ 
Y x
1+ 2 .
k=1
k
Does this converge? To check the definition, for each K ∈ N consider the partial
product
K 
Y x
fK (x) := 1+ 2 .
k=1
k
To show that limK→∞ fK (x) exists, fix an n ∈ N and consider the sequence [xn ]fK (x)
as K → ∞. Is this sequence eventually constant? No, not for all n ∈ N – in
particular not for n = 1. To be precise, the sequence
K
1
X 1
[x ]fK (x) =
k=1
k2
is not eventually constant as K → ∞. Therefore, this infinite product is not con-
vergent in the ring of fomal power series R[[x]].
Examples 7.11(d) and 7.13 might seem strange to you, since the sequence
of coefficients of x1 converges as a sequence of real numbers, as does every other
sequence of coefficients in these examples. That is, you would like to make use
of the concept of convergence in the coefficient ring R (in this case, the field of
real numbers). A general coefficient ring R has no such “topological” structure,
which is why we require that the coefficient sequences be eventually constant. (In
Exercise 12.12 we have occasion to discuss and employ a more flexible definition of
convergence for a sequence of formal power series over a “normed” ring.)
The proof of the following proposition is left as an important exercise.
Proposition 7.14. Let (fk (x) : k ∈ N) be an infinite sequence of formal power se-
ries in R[[x]]. Assume that there are only finitely many k ∈ N for which [x0 ]fk (x) =
−1. Then the followingP conditions are equivalent:
(a) The infinite sum ∞ k=0 fk (x) converges;
(b) For every J ∈ N, there
Q are only finitely many k ∈ N such that I(fk ) ≤ J;
(c) The infinite product ∞ k=0 (1 + fk (x)) converges.

At last, we turn to a discussion of the operation of composition of formal

Laurent series. We restrict ourselves to the case in which P
R is a field, so that R((x))
is also a field. Given f (x) = ∞ n ∞ j
P
a
n=I(f ) n x and g(x) = j=I(g) bj x in R((x)), we
will determine the conditions under which f (g(x)) is a well–defined Laurent series.
Of course, the symbol f (g(x)) is to be interpreted as
∞
X K
X
f (g(x)) := an g(x)n := lim an g(x)n .
K→∞
n=I(f ) n=I(f )

There are a few cases. If g(x) = 0 then g(x)n does not exist for any negative integer
n. Thus, if g(x) = 0 then f (g(x)) = f (0) exists if and only if I(f ) ≥ 0, in which
case f (0) = [x0 ]f (x). Assume now that g(x) 6= 0, so that g −1 (x) does exist in
the field R((x)). If f (x) has only finitely many nonzero coefficients then f (g(x))
is a polynomial function of g(x) and g −1 (x), and therefore is an element of R((x)).
Finally, assume that f (x) has infinitely many nonzero coefficients. Therefore, for
every N ∈ N there is an n ≥ N such that an 6= 0. Notice that (since R is an
integral domain) the index of an g(x)n is nI(g), n times the index of g(x). Therefore,
if I(g) ≤ 0 then condition (b) of Proposition 7.14 is violated for the sequence
(an g(x)n : n ≥ I(f )), so that the infinite summation
X∞
f (g(x)) = an g(x)n
n=I(f )

is not defined. Conversely, if I(g) > 0 then condition (b) of Proposition 7.14 is
satisfied, and f (g(x)) does exist. In summary, we have proved the following.
Proposition 7.15. Let f (x) and g(x) be formal Laurent series in R((x)), in which
R is a field. Then f (g(x)) is well–defined if and only if one of the following cases
holds:
(i) g(x) = 0 and I(f ) ≥ 0;
(ii) g(x) 6= 0 and f (x) has only finitely many nonzero coefficients;
(iii) g(x) 6= 0 and I(g) > 0.
Under some circumstances, it is useful to think of a formal power series f (x) ∈
R[[x]] as a “change of variables” by considering u := f (x) as another variable itself.
Of course, this u does depend on x, but one can consider the ring R[[u]], which will
be a subring of R[[x]]. The most interesting case is that in which R[[u]] = R[[x]],
which occurs exactly when there is a formal power series g(u) ∈ R[[u]] such that
x = g(u). These two equations u = f (x) and x = g(u) imply that x = g(f (x)) and
u = f (g(u)), which is called an invertible change of variables.
Proposition 7.16. Let R be a field, and let f (x) be a formal power series in R[[x]].
There exists g(u) ∈ R[[u]] such that x = g(f (x)) and u = f (g(u)) if and only if
either I(f ) = 1, or f (x) = a0 + a1 x with both a0 and a1 nonzero. If such a g(u)
exists then it is unique.
Proof. Consider a pair of formal power series such that x = g(f (x)) and u = f (g(u)).
First, if f (x) = 0 then there is clearly no g(u) ∈ R[[u]] such that u = f (g(u)),
so that this case does not arise.
Second, consider the case in which f (x) = ∞ n
P
n=0 an x has a nonzero constant
term a0 6= 0. In order for the composition g(f (x)) to be well-defined, g(u) =
P ∞ j
j=0 bj x must have only finitely many nonzero coefficients, by Proposition 7.15.
Since f (g(x)) = x and a0 6= 0, it follows that b0 6= 0 as well (for otherwise, if
b0 = 0 then [x0 ]f (g(x)) = a0 6= 0, contradicting f (g(x)) = x). Now, since b0 6= 0,
for the composition f (g(u)) to be well-defined, f (x) must have only finitely many
nonzero coefficients, by Proposition 7.15. That is, f (x) and g(u) are polynomials
with nonzero constant terms. Now both f (g(u)) and g(f (x)) are polynomials of
degree deg(f ) · deg(g), and hence deg(f ) = deg(g) = 1. From f (x) = a0 + a1 x and
g(u) = b0 + b1 u we see that x = g(f (x)) = b0 + b1 a0 + b1 a1 x, so that b0 + b1 a0 = 0 and
b1 a1 = 1. That is, b1 = a−1 −1
1 and b0 = −a0 a1 , so that g(u) is uniquely determined.
One easily checks that f (g(u)) = u as well, finishing this case.
P∞ Finally, consider a nonzero f (x) ∈ R[[x]] with index at least one. Let f (x) =
n
n=1 an x be given P
– we are assuming that a0 = 0. To begin with, we seek a formal
power series g(u) = ∞ j
j=0 bj u such that g(f (x)) = x. Expanding this, we have
∞ ∞ ∞
!j
X X X
j n
x = g(f (x)) = bj f (x) = bj an x
j=0 j=0 n=1
∞
X ∞
X X
= xm bj an1 an2 · · · anj .
m=0 j=0 n1 +n2 +···+nj =m

In the inner summation, since a0 = 0 we need only consider those j–tuples (n1 , . . . , nj )
such that each ni ≥ 1. Comparing coefficients of like powers of x, we see that for x0
we have
0 = b0 ,
1
for x we have
1 = b1 a1 ,
m
and for x with m ≥ 2 we have
Xm X
0= bj an1 an2 · · · anj .
j=1 n1 +n2 +···+nj =m

(The outer summation may be terminated at j = m because each ni ≥ 1 and

n1 + n2 + · · · + nj = m, and when j = 0 the inner summation is empty.)
Now let’s solve these equations for the coefficients bj of g(u). That b0 = 0 is
immediate, and b1 exists if and only if a1 6= 0, since R is a field. This shows that if
g(u) exists then I(f ) = 1. Conversely, assume that I(f ) = 1, so that a1 6= 0 – then
b1 := a−1
1 exists. For all m ≥ 2 we have
m−1
X X
bm = −bm
1 bj an1 an2 · · · anj .
j=1 n1 +n2 +···+nj =m

The RHS is a polynomial function of {a1 , . . . , am , b1 , . . . , bm−1 }, so that these equa-

tions can be solved uniquely by induction on m ≥ 2 to determine the coefficients
of g(u) in the case I(f ) = 1. This establishes existence and uniqueness of a power
series g(u) such that g(f (x)) = x when I(f ) = 1.
Now, in the case I(f ) = 1 the power series g(u) we have constructed also has
index one: I(g) = 1. We want to show that f (g(u)) = u as well. By the preceeding
argument, there is a unique formal power series h(x) such that h(g(u)) = u. Let’s
substitute u = f (x) into this – we obtain h(g(f (x))) = f (x). Since g(f (x)) = x
this reduces to h(x) = f (x), so that f (g(u)) = u, as desired. This completes the
proof. 
 The unique formal power series g(u) guaranteed by Proposition 7.16 is referred
to as the compositional inverse of f (x), and is sometimes denoted by f <−1> (u).
Proposition 7.16 is only part of the truth, as the following example shows.
Example 7.17. Consider the rational function f (x) = (1 + x)/(1 − x). As a formal
power series we have
1+x
= 1 + 2x + 2x2 + 2x3 + 2x4 + · · ·
1−x
Algebraically, we can solve u = f (x) for x as follows: u(1 − x) = 1 + x, so that
u − 1 = x(1 + u), so that x = (−1 + u)/(1 + u). Hence, x = g(u), where
−1 + u
g(u) = = −1 + 2u − 2u2 + 2u3 − 2u4 + · · ·
1+u
Now, even though u = f (x) and x = g(u), neither of the compositions f (g(u)) nor
g(f (x)) are well–defined, by Proposition 7.15.
The trouble with Example 7.17 is only that the compositions of these for-
mal power series do not converge according to Definition 7.10. To circumvent this
problem, we can define composition of rational functions instead.
Definition 7.18. Let f (x) = p(x)/q(x) and g(u) be rational functions. The com-
position of g(u) into f (x) is defined to be the rational function
p(g(u))
f (g(u)) := .
q(g(u))
Notice that since p(x) and q(x) are polynomials, the expressions p(g(u)) and q(g(u))
are well–defined rational functions.
Using this definition, all the operations in Example 7.17 are well-defined, re-
solving the difficulty.

7. Exercises.

1. Let R be a commutative ring. For a ∈ R consider the function µa : R → R

defined by µa (r) := ar for all r ∈ R.
(a) Show that if R is an integral domain and a 6= 0, then µa : R → R is an
injection.
(b) Show that if R is a finite integral domain then R is a field. (The ring Z of
integers is an integral domain which is not a field. Thus, finiteness of R is essential
for this problem. See Exercise 1.4.)

2. Let R be a commutative ring.

(a) Show that if R is an integral domain, then R[x] is an integral domain.
(b) Show that neither of R[[x]] nor R(x) contains the other.
(c) Show that if R is a field then R(x) is a proper subset of R((x)).
(d) Find an element of Z(x) which is not in Z((x)).
(e) Show that R[[x]][y] is a proper subset of R[y][[x]].

3. Recall the notation of Example 7.8.

P∞ y+n−1
(a) Show that in R[y][[x]], (1 − x)−y =


n=0 n
xn .
(b) Show that in R[y, z][[x]],
1 1 1
y+z
= · .
(1 − x) (1 − x) (1 − x)z
y

4. Let f (x) and g(x) be in R((x)). Show that

d
(f (x)g(x)) = f 0 (x)g(x) + f (x)g 0 (x).
dx

5. Prove Proposition 7.14.

6. Define a sequence of formal power series in Z[[x]] by f0 (x) := 1, f1 (x) := 1, and

fk+1 (x) := fk−1 (x) + xk fk (x) for all k ≥ 1. Prove that the limit limk→∞ fk (x) exists.

7. Define a sequence of formal power series in Z[[x]] by g0 (x) := 1, and gk+1 (x) :=
(1 − xgk (x))−1 for all k ∈ N.
(a) Prove that the limit g(x) = limk→∞ gk (x) exists.
(b) Show that g(x) satisfies the equation g(x) = (1 − xg(x))−1 , and thus is the
generating function for SDLPs in Theorem 6.9.

8. Consider the Chain Rule: for f (x) and g(x) in R((x)) such that f (g(x)) is
defined,
d
f (g(x)) = f 0 (g(x))g 0 (x).
dx
(a) Prove this for f (x) and g(x) in R[[x]].
(b) Prove this for f (x) and g(x) in R((x)).

9. Does the following limit exist in R[[x]]? Explain.

 x k
lim 1 + .
k→∞ k

10. Does the following limit exist in R((x))? Explain.

x−k
lim
k→∞ 1 − xk

11. Show that, as a sequence of formal power series in Z[[q]],

 
a+b 1
lim = .
a→∞ b q (1 − q)(1 − q 2 ) · · · (1 − q b )

12(a) Show that if f (x) ∈ R[[x]] is such that [x0 ]f (x) = 1, then log(f (x)) con-
verges.
12(b) With f (x) as in part (a), show that
d d
log(f (x)) = f −1 (x) f (x).
dx dx
12(c) Show that log(exp(x)) = x.
12(d) Show that   
1 1
exp log = .
1−x 1−x

7. Endnotes.
What we have in this section is just a tiny glimpse into the subject of com-
mutative algebra. Most of the motivation for this subject is quite separate from
the concerns of enumerative combinatorics – it aims towards algebraic geometry,
which describes sets of solutions to a collection of polynomial equations, among
other things. If you want to read up on this I recommend the following books, with
the caveat that they are really intended for graduate students.
• M.F. Atiyah and I.G. Macdonald, “Introduction to Commutative Algebra,”
Addison–Wesley, Reading MA, 1969.

• D. Eisenbud, “Commutative Algebra – with a view toward Algebraic Geometry,”

Graduate Texts in Mathematics, 150, Springer–Verlag, New York, 1995.

• J.M. Ruiz, “The Basic Theory of Power Series,” Braunschweig Vieweg, 1993.

The last of these also develops the foundations of geometry for categories other
than the algebraic one. It is all very fascinating stuff, but quite complicated, and
not really relevant to our present purpose. More down–to–earth expositions of what
we need of formal power series are given in Chapter 2 of

• H.S. Wilf, “Generatingfunctionology,” Academic Press, New York, 1994

and in Chapter 3 of

• C.D. Godsil, “Algebraic Combinatorics,” Chapman and Hall, New York, 1993.
8. The Lagrange Implicit Function Theorem.

The topic of this section – the Lagrange Implicit Function Theorem – is the
most widely applicable technique for the enumeration of recursively defined
structures. As we saw in Section 6, recursive structure leads to a functional equation
for the relevant generating function. When this equation is quadratic it can be solved
by the Quadratic Formula, as in Section 6. In most cases, however, the equation
is not quadratic and simple high–school tricks do not suffice. Instead, Lagrange’s
Theorem is perfectly suited to such tasks.
Theorem 8.1 (LIFT). Let K be a commutative ring which contains the rational
numbers Q. Let F (u) and G(u) be formal power series in K[[u]] such that [u0 ]G(u)
is invertible in K.
(a) There is a unique (nonzero) formal power series R(x) in K[[x]] such that
R(x) = x G(R(x)).
(b) The constant term of R(x) is 0, and for all n ≥ 1,
1
[xn ]F (R(x)) = [un−1 ]F 0 (u)G(u)n .
n
Before proceeding to the proof, let’s apply this theorem to Example 6.15.
Example 8.2. As in Example 6.15, let W be the set of ternary rooted trees, and
let W (x) be the generating function for W with respect to number of nodes. We
have derived the functional equation
W = x(1 + W )3
for this generating function. This fits perfectly into the hypothesis of LIFT, using
K = Q, F (u) = u and G(u) = (1 + u)3 . Thus, we calculate that the number of
ternary rooted trees with n ≥ 1 nodes is
 
n 1 n−1 3n 1 3n
[x ]W (x) = [u ](1 + u) = .
n n n−1
That’s a piece of cake!

In order to prove Lagrange’s Theorem we need to develop a few more facts

about formal Laurent series. These have to do with the formal residue operator,
which is merely the operator [x−1 ] that extracts the coefficient of x−1 from a formal
Laurent series. (The terminology is by analogy with the case K = C of complex
numbers and the Cauchy Residue Theorem.) We require three facts about it, and
then we can prove LIFT.
Lemma 8.3. Let F (x) be a formal Laurent series. Then
d
[x−1 ] F (x) = 0.
dx
P∞ n
Proof. If F (x) = n=I(F ) an x then
∞
−1 d −1
X
[x ] F (x) = [x ] nan xn−1 = 0a0 = 0.
dx
n=I(F )


Lemma 8.4. Let F (x) and G(x) be formal Laurent series. Then
[x−1 ]F 0 (x)G(x) = −[x−1 ]F (x)G0 (x).
Proof. This follows by applying Lemma 8.3 to F (x)G(x), since
d
(F (x)G(x)) = F 0 (x)G(x) + F (x)G0 (x),
dx
by Exercise 7.3. 
Lemma 8.5 (Change of Variables). Let F (u) and B(x) be formal Laurent series.
Assume that I(B) > 0, and that [xI(B) ]B(x) is invertible in K. Then
[x−1 ]F (B(x))B 0 (x) = I(B)[u−1 ]F (u).
Proof. First, we consider the case in which F (u) = uk for some integer k. If k 6= −1
then we may write the LHS of the formula as
1 d
[x−1 ]B(x)k B 0 (x) = [x−1 ] B(x)k+1 = 0,
k+1 dx
−1 k
by Lemma 8.3. Also, if k 6= −1 then [u ]u = 0 on the RHS, so the formula holds
in this case. In the remaining case, k = −1, we have I(B)[u−1 ]u−1 = I(B) on the
RHS. On the LHS we have [x−1 ]B(x)−1 B 0 (x). To compute this, write
B(x) = cxI(B) H(x),
in which c ∈ K is invertible and H(x) is a formal power series with [x0 ]H(x) = 1.
By Proposition 7.5, H(x)−1 exists and is a formal power series – also
B(x)−1 = c−1 x−I(B) H(x)−1
and
B 0 (x) = cxI(B) H 0 (x) + cI(B)xI(B)−1 H(x).
Therefore,
[x−1 ]B(x)−1 B 0 (x) = [x−1 ](c−1 x−I(B) H(x)−1 )(cxI(B) H 0 (x) + cI(B)xI(B)−1 H(x))
= [x−1 ](H(x)−1 H 0 (x) + I(B)x−1 ) = I(B),
since H(x)−1 H 0 (x) is a formal power series. This establishes the formula whenever
F (u) = uk for some integer k ∈ Z.
Now consider any formal Laurent series F (u) = ∞ k
P
k=I(F ) ak u . We have
∞
X
0
F (B(x))B (x) = ak B(x)k B 0 (x),
k=I(F )

and so, by using the cases we have already proven, we see that
X∞
−1 0
[x ]F (B(x))B (x) = ak [x−1 ]B(x)k B 0 (x)
k=I(F )
∞
X
= ak I(B)[u−1 ]uk
k=I(F )
∞
X
−1
= I(B)[u ] ak uk = I(B)[u−1 ]F (u).
k=I(F )

This proves the lemma. 

Now we can prove the Lagrange Implicit Function Theorem. I admit that this
argument can be verified line–by–line, but that it does not convey an overall sense of
understanding. For that deeper understanding, I present a second – combinatorial
– proof of LIFT in Section 13. This second proof is usually postponed until C&O
430/630.

Proof of LIFT. For part (a), let R(x) = ∞

P n
P∞ k
n=0 rn x , and let G(u) = k=0 gk u
with g0 6= 0 in K. (We do not need g0 to be invertible for this part of the proof.)
Consider the equation R(x) = xG(R(x)). We will show that it has a unique solution
R(x) (which is nonzero) by showing that for each n ∈ N, rn is determined by the
previous coefficients r0 , r1 , . . . , rn−1 and by the coefficients g0 , g1 , . . . , gn−1 of G(x),
and that a suitable value for rn always exists. First of all, notice that
r0 = [x0 ]R(x) = [x0 ]xG(R(x)) = 0,
P∞
so we may write R(x) = n=1 rn xn instead. Next, expand both sides of the equation
R(x) = xG(R(x)) and equate like powers of x:
∞ ∞ ∞
!k
X X X
rn x n = x gk rn x n
n=1 k=0 n=1
∞ ∞
!
X X X
= xn gk rn1 rn2 · · · rnk .
n=1 k=0 n1 +n2 +···+nk =n−1
The inner sum on the RHS is over all ordered k–tuples of positive integers which
sum up to n − 1. For a given value of n, this implies that k ≤ n − 1, and so for
every n ≥ 1,
Xn−1 X
rn = gk rn1 rn2 · · · rnk .
k=0 n1 +n2 +···+nk =n−1
Notice that since r1 = g0 6= 0, the index of R is I(R) = 1. The proof of part (a)
is completed by showing that rn is a polynomial function of g0 , . . . , gn−1 . This is
accomplished by an easy induction on n ∈ N, which we leave to the reader.
For this proof of part (b) we require g0 to be invertible in K, so that G(u)−1
exists in K[[u]]. Consider the formal power series P (u) := uG(u)−1 . Let R(x) be
defined as in part (a), and make the change of variables u := R(x). Then, since
R(x) = xG(R(x)), we get
x = R(x)G(R(x))−1 = uG(u)−1 = P (u),
so that x = P (u) is the change of variables inverse to u = R(x). By Proposition
7.16 both of the compositions x = P (R(x)) and u = R(P (u)) are well–defined.
Now, for n > 0 we may calculate, using Lemma 8.4, that
 
n −1 −1−n 1 −1 d −n
[x ]F (R(x)) = [x ]x F (R(x)) = − [x ] x F (R(x))
n dx
1 −1 −n 0 1
= [x ]x F (R(x))R0 (x) = [x−1 ]H(R(x))R0 (x),
n n
in which we have put H(u) := P (u) F (u), so that H(R(x)) = x−n F 0 (R(x)).
−n 0

Continuing, by Lemma 8.5 we have

[x−1 ]H(R(x))R0 (x) = I(R)[u−1 ]H(u) = [u−1 ]P (u)−n F 0 (u)
= [u−1 ]u−n G(u)n F 0 (u)
= [un−1 ]F 0 (u)G(u)n .
This completes the proof. 
I warned you. . . it makes sense line–by–line. . . but where the heck did all that
algebra come from?! All I can say is that in Section 13 we find a way to interpret this
formula combinatorially and prove it in a conceptual manner (and under slightly
weaker hypotheses). In the meantime, here is an illustration of the method in
practice.
Example 8.6. What is the expected number of terminals among all ternary rooted
trees with n nodes? Let τ (T ) denote the number of terminals of T ∈ W, and consider
the bivariate generating function
X
W (x, y) := xn(T ) y τ (T ) .
T ∈W
Analogously with Question 6.2, the average we seek is An /Tn in which
 
n 1 3n
Tn = [x ]W (x, 1) =
n n−1
from Example 8.2, and 
n ∂

An = [x ] W (x, y) .
∂y y=1
To compute An we begin by deriving a functional equation for W (x, y) from the
recursive structure of ternary rooted trees:
W
{} × ({∅} ∪ W)3
T ↔ (, L, M, R)
n(T ) = 1 + n(L) + n(M ) + n(R)

1 if L = M = R = ∅,
τ (T ) =
τ (L) + τ (M ) + τ (R) otherwise.
This yields the functional equation
W = x(y + 3W + 3W 2 + W 3 )
for the generating function W (x, y). Now LIFT applies with K = Q(y), F (u) = u,
and G(u) = y + 3u + 3u2 + u3 . The following calculation is a bit sneaky, so read
carefully and think about why each step is valid.
 
n ∂ ∂ n
 
An = [x ] W (x, y) = [x ]W (x, y)
∂y y=1 ∂y y=1

∂ 1 n−1 
= [u ](y + 3u + 3u2 + u3 )n 
∂y n y=1

1 n−1 ∂ 
= [u ] (y + 3u + 3u2 + u3 )n 
n ∂y y=1
1 n−1 
= [u ] n(y + 3u + 3u2 + u3 )n−1 y=1
n  
n−1 3n−3 3n − 3
= [u ](1 + u) = .
n−1
Therefore, the average number of terminals among all ternary rooted trees with n
nodes is
3n−3


An n−1 (2n + 1)(2n)(2n − 1)
= 1 3n
= ,
Tn n n−1
3(3n − 1)(3n − 2)
after some simplification. As n → ∞ this is asyptotic to 8n/27, so that in a large
random ternary rooted tree one expects about 8/27 = 0.296 of the nodes to be
terminals.
8. Exercises.

1. Fix a positive integer c. For each n ∈ N, determine the number of plane planted
trees with n nodes in which the number of children of each node is divisible by c. (I
remind you that 0 is divisible by every such c.)

2. For a plane planted tree T , let h(T ) denote the number of nodes of T which
have an even number of children. For each n ∈ N, determine the average value of
h(T ) among all the PPTs with n nodes.

3. Fix an integer k ≥ 2. A k–ary rooted tree T has a root node , and each node
may have at most one child of each of k “types”. (The case k = 2 gives BRTs, and
the case k = 3 gives TRTs.)
kn
(a) Show that the number of k–ary rooted trees with n nodes is n1 n−1


.
(b) Show that, as n → ∞, the expected number of terminals among all k–ary
rooted trees with n nodes is asymptotically (1 − 1/k)k n.

4. For a plane planted tree (PPT) T , let f (T ) be the number of nodes of T with
at least three children. Show that for n ≥ 4, the average value of f (T ) among all
the PPTs with n nodes is (n2 − 3n)/(8n − 12).

5. If an SDLP P touches the diagonal x = y at points

(0, 0) = (k0 , k0 ), (k1 , k1 ), . . . , (kr , kr ) = (n, n),
then the sub–path of P between the points (ki−1 , ki−1 ) and (ki , ki ) is called the i–th
block of P . Show that the expected number of blocks among all SDLPs to (n, n) is
3n/(n + 2).

6. For a plane planted tree (PPT) T , let d(T ) be the degree of the root nodes
of T . Show that for n ≥ 1, the average value of d(T ) among all the PPTs with n
nodes is (3n − 3)/(n + 1).

7. For a plane planted tree T , a middle child is a non–root node which is neither
the leftmost nor the rightmost child of its parent. Let p(T ) denote the number of
middle children in T . For each n ∈ N, determine the average value of p(T ) among
all the PPTs with n nodes.
8. (a) Let α and x be indeterminates. Find a formal power series f (y) such that
exp(αx) = f (x exp(−x)).
(b) Let β be another indeterminate. Prove that
n  
n−1
X n
(α + β)(n + α + β) = αβ (k + α)k−1 (n − k + β)n−k−1 .
k=0
k
(For n ≥ 1, the polynomial z(n + z)n−1 is known as an Abel polynomial.)

8. Endnotes.
Incidentally, Lagrange was not a combinatorialist. In fact, combinatorics as
such did not even exist during his lifetime (with the exception of a few things which
Euler investigated). Lagrange discovered this theorem in order to solve functional
equations which he derived in calculations of the orbital motion of the moon. These
calculations were by far the most accurate ever done up to that time, and for many
decades thereafter. All without electricity, too, of course!
For some entertaining reading, and somewhat fictionalized biographies of fa-
mous mathematicians, I recommend the following dated and sexistly titled classic:

• E.T. Bell, “Men of Mathematics,” Simon & Schuster, New York, 1986.

The proof of the Lagrange Implicit Function Theorem presented here is adapted
from Goulden and Jackson’s monumental book:

• I.P. Goulden and D.M. Jackson, “Combinatorial Enumeration,” John Wiley &
Sons, New York, 1983.