Supplemental note on formal power series
Supplemental note on formal power series
When we are manipulating generating series, we are doing so according to the algebra of formal power
series. For every day purposes, you don’t need to worry about this algebra – the definitions have
been made precisely so that if you just manipulate the series following the rules you expect you will
essentially always be doing the right thing. However, from a more mathematical perspective, that isn’t
very satisfying, and so in this note we will go over the foundations.
The first thing we need is the definition. A formal power series is an expression of the form a0 +
a1x
n + a2x
n + · · ·+ akxk + · · · =
∑∞
n=0 anx
n where a0, a1, a2, . . . is a sequence of real numbers.1
Two formal power series are equal if and only if their sequences of coefficients are equal. That is
a0 + a1x+ a2x
2 + · · · = b0 + b1x+ b2x2 + · · · if and only if a0 = b0, a1 = b1, a2 = b2, · · · .
Intuitively, formal power series are a way to store a sequence. Formal in this case means that formal
power series are defined to follow algebraic rules which have the form of those for analytic series, but
they do not have any independent meaning as functions.
As an example, the geometric series
∑
n≥0 x
n is the formal power series associated to the sequence
1, 1, 1, . . .. Polynomials are also examples of formal power series. Specifically polynomials are those
formal power series where the coefficients are eventually all 0. There are many more examples in
the course notes. All our generating series are formal power series; they are the formal power series
associated to the counting sequence for the objects being counted.
Operations
Operations for formal power series are defined to match those which series expansions of functions in-
herit from the functions, but note that these definitions make no reference to convergence or functions.
Addition and multiplication
Let A(x) =
∑∞
n=0 anx
n and B(x) =
∑∞
n=0 bnx
n. Then the sum A(x) + B(x) is defined to be the formal
power series
A(x) +B(x) =
∑
n≥0
(an + bn)x
n.
In other words the coefficient of xn in A(x) +B(x) is defined to be an + bn.
Let A(x) =
∑∞
n=0 anx
n and B(x) =
∑∞
n=0 bnx
n. Then the sum A(x)B(x) is defined to be the formal
power series
A(x)B(x) =
∞∑
n=0
n∑
k=0
akbn−kx
n.
In other words the coefficient of xn in A(x)B(x) is defined to be
∑n
k=0 akbn−k. That looks a little messy,
but it is exactly what you would get from multiplying out polynomials or series in the analytic sense.
With this addition and multiplication, formal power series form a ring, but you don’t need to know what
a ring is for this course, so this sentence is just for folks who have done some additional reading.
Multiplicative inverse
Two other very important operations on formal power series are multiplicative inverse and composi-
tion, however these two operations are different from addition and multiplication because they are not
1In fact any ring can be substituted for the real numbers, but for this course, real numbers as coefficients will suffice, in fact
rational numbers will suffice.
FALL 2021 MATH 239: INTRODUCTION TO COMBINATORICS Page 1
Supplemental note on formal power series
defined for all formal power series or for all pairs of formal power series.
Let us first consider the multiplicative inverse. Let A(x) =
∑∞
n=0 anx
n be a formal power series. The
multiplicative inverse of A(x), if it exists, is the formal power series C(x) =
∑∞
n=0 cnx
n satisfying
A(x)C(x) = 1.
We write C(x) = 1
A(x)
in order to say that C(x) is the multiplicative inverse of A(x).
In order to see when the multiplicative inverse exists, let us consider in more detail what A(x)C(x) =
1 means. We know from the definition of multiplication of formal power series that A(x)C(x) =∑∞
n=0 (
∑n
k=0 akcn−k)x
n. We know from the definition of equality of formal power series that for this
to be equal to the formal power series 1 = 1 + 0x+ 0x2 + 0x3 + · · · then we must have
1 = a0c0
0 = a1c0 + a0c1
0 = a2c0 + a1c1 + a0c2
…
Now consider solving this system. Provided that a0 6= 02 we can write c0 = 1/a0, and then from the
second line we can bring the terms which don’t contain c1 to the other side and write c1 = −a1c0/a0 =
−a1/a20. Continuing likewise, we can solve the kth row for ck−1 simply by bringing the terms other than
a0ck−1 to the other side, dividing by a0 and noting that everything on the other side is either an ai or is
a cj that was solved for in a previous row.
By this argument we see that C(x) exists if a0 6= 0. In the other direction if a0 = 0 then the first
equation is 1 = 0, so C(x) exists if and only if a0 6= 0 and when it exists the coefficients of C(x) can be
calculated recursively by the system of equations above.
You’ve already been working with at least one example of a multiplicative inverse: the multiplicative
inverse of 1− x is 1 + x+ x2 + · · · (try proving it yourself using the system above). In other words
1
1− x
=
∑
n=0
∞xn.
This is a true equation in formal power series according to the definitions we have given; no need for a
convergence condition.
Composition and valid operations
We would also like to have composition of formal power series. Let A(x) =
∑∞
n=0 anx
n and B(x) =∑∞
n=0 bnx
n be formal power series; then we would like
A(B(x)) =
∞∑
n=0
anB(x)
n.
2If you’re working in a different ring, you need that a0 is invertible.
FALL 2021 MATH 239: INTRODUCTION TO COMBINATORICS Page 2
Supplemental note on formal power series
The question is when is this well defined. Let’s start writing out what it would be and see what the
problem is
A(B(x)) =
∞∑
n=0
anB(x)
n
= a0 + a1B(x) + a2B(x)
2 + · · ·
= a0 + a1(b0 + b1x+ b2x
2 + · · · ) + a2(b0 + b1x+ b2x2 + · · · )2 + · · ·
= a0 + a1(b0 + b1x+ b2x
2 + · · · ) + a2(b20 + 2b1b0x+ (b
2
1 + 2b2b0)x
2 + · · · ) + · · ·
= a0 + a1b0 + a2b
2
0 + · · ·+ 2b1b0x+ 2b1b0a2x+ · · ·
The coefficient of x0 in A(B(x)) will look like:
a0 + a1b0 + a2b
2
0 + · · · .
Now this is a problem. This is not something that makes sense in general in the world of formal power
series. In this formal context, we don’t have any rules for giving infinite sums values and hence having
them as coefficients. But it does make sense sometimes. If b0 = 0 the coefficient of x0 in A(B(x)) is a0
which is fine. If A(x) is a polynomial then the coefficient of x0 in A(B(x)) is a finite sum and hence is
also ok.
It turns out that these are the only ways to fix the problem and that all the other coefficients work out
as well in these cases, and so A(B(x)) is well defined if and only if b0 = 0 or A(x) is a polynomial. Try
to work out the details of the proof yourself.
At this point you might be feeling a need for a more general understanding of when an operation on
formal power series makes sense and when it doesn’t. The usual way of doing this involves defining
a topology on the algebra of formal power series and convergence in that topology. For the present
purposes let’s do something a little simpler, but also a little more ad-hoc. Say we have an operation
which takes some formal power series as input and gives a formal power series as output. Concretely,
how could we implement this operation? All a formal power series has is its sequence of coefficients,
and if we are working with it in a computer, all we can have is a finite number of initial coefficients. We
want to be able to give our output series in the same way, by giving coefficients. So, for the operation
to be valid, then in order to obtain some particular coefficient of the output, we can use only finitely
many coefficients of the input.
We can use this notion of valid to reconsider what we said above about compositions. Our calculation
above showed that when b0 6= 0 and A(x) is not a polynomials then composition is not valid because to
obtain the coefficient of x0 we needed infinitely many coefficients of A(x).
Other operations
There are many other operations on formal power series. We will not need them in this course, but
generally they behave like you would expect from calculus, while being defined in purely algebraic
terms. For example, if A(x) =
∑
n≥0 anx
n then the formal derivative A′(x) is defined to be
A′(x) =
∑
n≥0
(n+ 1)an+1x
n
It turns out that this notion of formal derivative satisfies the usual properties of the derivative (sum
rule, product rule, chain rule), but these need to be proved from the definitions of formal power series.
Try it, they are good exercises in manipulating formal power series.
In all cases the operations line up with what you would expect from analytic series. It is this which
makes it possible for you to basically ignore this entire document and just manipulate generating series
in the obvious way. It also means that when the series do happen to converge, all our notions coincide
with the analytic notions and from there we get analytic combinatorics, but that’s another story.
FALL 2021 MATH 239: INTRODUCTION TO COMBINATORICS Page 3