Chapter 4: Formal Series and Generating Functions #

Since there is a great conformity between the Operations in Species, and the same Operations in common Numbers... I cannot but wonder that no body has thought of accommodating the lately discover’d Doctrine of Decimal Fractions in like manner to Species... especially since it might have open’d a way to more abstruse Discoveries.

— Issac Newton

The difference between a sequence that stops somewhere and one that has no end is awful. No one, unless spiritually unborn or dead, can contemplate that gulf without emotions that take hold of the infinite and everlasting.

— Cassius Keyser

Let $\mathcal{C}$ be a combinatorial class with counting sequence $$ (c_n) = c_0,c_1,\dots $$ and generating series $$ C(z) = \sum_{n=0}^{\infty} c_nz^n. $$ As discussed in Chapter 1, the generating series $C(z)$ forms a data structure for the sequence $c_n,$ allowing us to manipulate $c_n$ implicitly through algebraic, differential, or functional equations satisfied by $C(z).$ The use of such a data structure is crucial for the development of effective algorithms in enumeration, and their implementation on a computer.

In this chapter we discuss formal series, which provide the algebraic background needed to define and compute with generating series. Techniques to derive equations satisfied by generating series of combinatorial classes are discussed in the next chapter.

Many students first encounter infinite series in the context of Taylor series (one of the most beautiful and impactful topics in all of mathematics) during a calculus course. Because Taylor series are used to represent actual functions, one must be careful which values are substituted into the series to make sure they converge. The basics of convergent series are recapped in the appendix at the end of this chapter.

There are many natural generating series that do not represent convergent series.

Example: The ratio test implies that the generating series $\sum_{n \geq 0} 2^nz^n$ for the class of binary strings counted by length converges when $|z|<1/2.$ In contrast, the ratio test implies that the generating series $\sum_{n \geq 0} n! z^n$ for the class of permutations does not converge at any point near the origin except the trivial case when $z=0.$

Instead of wasting time worrying about where a generating series converges, if it even does, we define formal series to get around the issue. As a bonus, formal series can be defined with coefficients in many algebraic structures beyond the real or complex numbers. For instance, when enumerating combinatorial classes with parameters we will consider iterated series in multiple variables.

Example: Let $b_{k,n}$ denote the number of binary strings of length $n$ with $k$ ones. Such a string is uniquely defined by picking $k$ indices from the set $\{1,\dots,n\}$ to place the ones, so $b_{k,n} = \binom{n}{k}.$ Formal power series will allow us to appropriately consider the bivariate generating series $$ B(x,y) = \sum_{k,n \geq 0} \binom{n}{k}x^ky^n = \sum_{n \geq 0}(1+x)^ny^n = \frac{1}{1-(1+x)y} $$ as a series in $y$ whose coefficients are polynomials in $x.$ Details on multivariate generating series, and justification for the computations in this example, are given in Part 3 of these notes.

Before defining formal series we must introduce some algebraic preliminaries.

Rings and Fields #

A ring is a set $R$ together with two operations $+$ and $\times$ that take any $a,b\in R$ and return elements $a+b$ and $a\times b$ in $R,$ together with two special distinct elements $0,1 \in R$ such that for all $a,b,c \in R,$

• $(a+b)+c = a + (b+c)$

• $a + b = b+a$

• $a + 0 = a$

• there exists $(-a) \in R$ such that $a + (-a) = 0$

• $(a \times b) \times c = a \times (b \times c)$

• $a \times 1 = 1 \times a = a$

• $a \times (b + c) = (a \times b) + (a \times c)$

• $(b + c) \times a = (b \times a) + (c \times a)$

These properties state, in order, that addition is associative and commutative (first two points), $0$ is the additive identity, additive inverses exist, multiplication is associative, $1$ is the multiplicative identity, and the distributive law holds on the left and the right.

Although these properties might seem abstract, they are crafted to capture the algebraic structure of objects the reader is probably already familiar with.

Example: The sets $\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ are all rings, as is the set $\mathbb{R}^{n \times n}$ of $n\times n$ real matrices, the set $\mathbb{Z}/n\mathbb{Z}$ of the integers modulo any fixed positive integer $n,$ the set $\mathbb{Q}[z]$ of polynomials with rational coefficients, and the set $\mathbb{Q}(z)$ of rational functions with rational coefficients. The set $\mathbb{N}$ is not a ring because, for instance, the element $1 \in \mathbb{N}$ has no additive inverse in $\mathbb{N}.$

Remark: By tradition, we use the symbols $0$ and $1$ for the additive and multiplicative identities in $R$ because their properties mirror the properties of $0$ and $1$ in the integers. Do not become confused between these special ring elements and the constants $0$ and $1.$ For instance, in the ring of $n\times n$ real matrices the additive identity is the all zeroes matrix and the multiplicative identity is the identity matrix.

Many of the rings in our last example have additional algebraic properties that hold often and imply additional structure that can be useful. We say

• $R$ is commutative if $a \times b = b \times a$ for all $a,b\in R,$
• $R$ has no zero divisors if $a \times b = 0$ implies $a=0$ or $b=0$ for all $a,b\in R.$

A commutative ring with no zero divisors is called an integral domain. A field is an integral domain where for any $a \in R$ with $a \neq 0$ there is another element $a^{-1} \in R$ (the multiplicative inverse of $a$) with $a \times a^{-1} = 1.$

Example: Going back to our previous examples,

• The ring $\mathbb{R}^{n \times n}$ of $n\times n$ real matrices is not commutative and does have zero divisors (two non-zero matrices multiplied together can yield the zero matrix).

• The ring $\mathbb{Z}/n\mathbb{Z}$ of integers modulo $n$ is always commutative. It is an integral domain precisely when $n$ is prime. In fact, the extended Euclidean algorithm can be used to construct multiplicative inverses and thus show that $\mathbb{Z}/p\mathbb{Z}$ is a field whenever $p$ is prime.

• The rings $\mathbb{Z}$ and $\mathbb{Q}[z]$ are integral domains but not fields (the elements $2 \in \mathbb{Z}$ and $z \in \mathbb{Q}[z]$ have no multiplicative inverses in their respective integral domains).

• The rings $\mathbb{Q},\mathbb{C},$ and $\mathbb{Q}(z)$ are fields.

It is common to drop the symbol $\times$ from expressions and write $ab$ for the product $a \times b,$ and to write $1/a$ for $a^{-1}$ when it exists.

Formal Power Series #

With these algebraic definitions out of the way, we are ready to define our main objects of study.

Let $R$ be an integral domain. The ring of formal power series with variable $z$ and coefficients in $R$ is the set $R[[z]]$ of formal expressions $$ \sum_{n=0}^{\infty} c_nz^n = c_0 + c_1z + c_2z^2 + \cdots $$ with each $c_j \in R.$ Given $$ A(z) = \sum_{n=0}^{\infty} a_nz^n \;\;\;\;\;\;\;\; B(z) = \sum_{n=0}^{\infty} b_nz^n$$ in $R[[z]]$ we define addition and multiplication for these formal expressions by $$ A(z) + B(z) := \sum_{n=0}^{\infty} (a_n + b_n) z^n $$ and $$ A(z)B(z) := \sum_{n=0}^{\infty} \left(\sum_{k=0}^n a_k b_{n-k} \right) z^n. $$ We write $[z^N]A(z)$ for the coefficient $a_N$ of $A,$ and also use the notation $A(0)$ for the constant $a_0.$

Remark: The definition of multiplication comes from collecting terms with the same powers of $z$ in the product $$ (a_0 + a_1z + \cdots) (b_0 + b_1z + \cdots) = (a_0b_0) + (a_0b_1 + a_1b_0)z + \cdots. $$

Although an element of $R[[z]]$ looks like a convergent power series, it is really just an abstract algebraic object encoding its sequence of coefficients like an array. We use series notation because most of the natural properties of convergent power series continue to hold for formal power series, and many formal power series do in fact represent convergent power series for various values of the parameter $z.$ However, if we want to use a property of convergent power series to argue about formal power series then we must first (re)prove the property for formal series.

Exercise: Prove that $R[[z]]$ is an integral domain under this definition of addition and multiplication.

Exercise: Prove that if addition were defined term-wise as above but we changed the definition of multiplication to $$ \sum_{n=0}^{\infty} a_nz^n \times \sum_{n=0}^{\infty} b_nz^n = \sum_{n=0}^{\infty} (a_n b_n) z^n $$ then the resulting ring would not form an integral domain.

We note that $R[[z]]$ is not a field because there are elements, such as $z,$ that do not have a multiplicative inverse.

Lemma 1: Let $R$ be an integral domain. A formal power series $A(z) = \sum_{n\geq0} a_nz^n$ has a multiplicative inverse in $R[[z]]$ if and only if its constant $a_0$ is invertible in $R.$

Example: Prove that $$ \frac{1}{1-2z} = \sum_{n \geq 0}2^n z^n $$ as formal power series in $\mathbb{Z}[[z]].$

Click for Answer

Let $A(z) = \sum_{n \geq 0}2^n z^n.$ By definition $\frac{1}{1-2z}$ is the power series that can be multiplied by $1-2z$ to give the constant $1$ (which we know exists because the constant term of $1-2z$ is invertible). Thus, we need to prove that $$ 1 = (1-2z) A(z) $$ using only properties of formal power series. If $N>0$ then the definition of multiplication in $\mathbb{Z}[[z]]$ implies $$ \begin{aligned} [z^N] {\Big(}(1-2z) A(z) {\Big)} &= [z^N]A(z) - 2[z^{N-1}]A(z) \\[+4mm] &= 2^N-2^N \\[+4mm] &= 0, \end{aligned} $$ and the constant term of $(1-z)A(z)$ is $1 \cdot 1 = 1.$ In other words, we have $$ 1 = (1-2z) \sum_{n \geq 0} 2^nz^n $$ as claimed.

A natural desire to divide by any power series leads to the following algebraic structure.

Let $R$ be an integral domain. The ring of formal Laurent series with variable $z$ and coefficients in $R$ is the set $$R((z)) = \left\{\sum_{n=\ell}^{\infty} c_nz^n : \ell \in \mathbb{Z} \text{ and each } c_j \in R \right\}.$$ Given $$ A(z) = \sum_{n=\ell}^{\infty} a_nz^n \;\;\;\;\;\;\;\; B(z) = \sum_{n=m}^{\infty} b_nz^n$$ in $R((z))$ we define addition and multiplication for these formal expressions by $$ A(z) + B(z) := \sum_{n=\min(\ell,m)}^{\infty} (a_n + b_n) z^n $$ and $$ A(z)B(z) := \sum_{n=\ell+m}^{\infty} \left(\sum_{k=\ell}^{n-m} a_k b_{n-k} \right) z^n, $$ where we set $a_n = 0$ if $n<\ell$ and $b_n=0$ if $n<m.$

Formal Laurent series are like formal power series, except they are allowed to have a finite number of terms with negative powers.

Example: The expansion $3z^{-5} - 7z^{-1} + 11z + \cdots$ is the start of a series in $\mathbb{Z}((z))$ but $\displaystyle\sum_{n = -\infty}^{\infty} z^n$ is not in $\mathbb{Z}((z)).$

The fact that $R((z))$ is a ring follows from an analogous argument to the fact that $R[[z]]$ is a ring. In fact, Lemma 1 above implies the following.

Corollary: If $K$ is a field then $K((z))$ is a field.

Because every integral domain lies inside its field of fractions, expanding from power series to Laurent series allows us to naturally solve linear equations involving formal power series. More generally, we can try to solve any algebraic equation involving formal power series. The algebraic closure of a field $K$ is the smallest field containing $K$ as a subfield (a field with the same structure as $K$ but potentially more elements) such that the roots of any polynomial in $K[z]$ lie in $K.$ It is a standard result of commutative algebra that (assuming the axiom of choice) every field has an algebraic closure, unique up to isomorphism.

The algebraic closure of the field of Laurent series $R((z))$ is the field of Puiseux series, which allows fractional powers as long as every power can be written over a common denominator. A full study of Puiseux series is beyond the scope of these notes, as we are mainly interested in power series solutions to algebraic equations. Instead, we will make use of the following result.

Generalized Binomial Theorem: Let $K$ be a field contained in the complex numbers (such as the rational numbers). If $\alpha=r/s$ for $r,s \in \mathbb{N}$ with $s>0$ then the equation $y^s = (1+z)^r$ has a solution $$ y(z) = \sum_{k \geq 0} \binom{\alpha}{k} z^k $$ in $K[[z]],$ where we extend the definition of the binomial coefficients to $\alpha \in \mathbb{Q}$ by setting $$ \binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}.$$ The equation $y^s = (1+z)^r$ has at most $s$ distinct solutions, obtained by multiplying the series $y(z)$ above by any of the numbers in the set $\{t \in K : t^s=1\}.$ We write $(1+z)^{\alpha}$ for the series solution $y(z)$ that begins with the constant 1.

The key to proving the generalized binomial theorem is to note that the basic algebraic operations of formal and convergent series are the same. In other words, if a convergent power series satisfies an algebraic equation then it still satisfies that equation when considered as a formal power series.

Exercise: If $s=1$ then $\binom{r}{k}=0$ if $k>r$ and the binomial theorem states $$ (1+z)^r = \sum_{k=0}^r \binom{r}{k} z^k $$ where $\binom{r}{k} = \frac{r!}{k!(r-k)!}.$ Give a proof of this polynomial identity directly using induction. Can you give a combinatorial proof?

Example: Find the coefficient of $z^n$ in the expansion of $(1+z)^{-1/2}$ as an element of $\mathbb{Q}[[z]]$ with constant term 1.

Click for Answer

The generalized binomial coefficient implies that the coefficient of interest is $$ \binom{-1/2}{n} = \frac{(-1/2)(-1/2-1)\cdots(-1/2-n+1)}{n!}. $$ Algebraic manipulation implies this term equals $$ \begin{aligned} &\;\;(-1)^n \, 2^{-n} \, \frac{(1)(3)(5)\cdots(2n-1)}{n!} \\[+4mm] &= (-1)^n \, 2^{-n} \cdot \frac{2^nn!}{2^nn!} \cdot \frac{(1)(3)(5)\cdots(2n-1)}{n!} \\[+4mm] &= (-1)^n 4^{-n} \frac{(2)(4)(6) \cdots (2n)}{n!} \cdot \frac{(1)(3)(5) \cdots (2n-1)}{n!} \\[+4mm] &= (-1)^n 4^{-n} \frac{(2n)!}{n! \, n!} \\[+4mm] &= (-1)^n 4^{-n}\binom{2n}{n}. \end{aligned} $$

Generating Series #

With all of the above out of the way, we define the generating series $C(z)$ of a sequence $(c_n)$ to be the formal power series with coefficients $c_n,$ and the generating series of a combinatorial class $\mathcal{C}$ to be the formal power series $C(z)$ in $\mathbb{Q}[[z]]$ defined by its counting sequence.

Exercise: Prove the identity $$ C(z) = \sum_{\sigma \in \mathcal{C}} z^{|\sigma|}$$ where $|\cdot|$ is the size function for the combinatorial class $\mathcal{C}.$

Example: Let $m_n$ denote the number of ways to make change for $n$ cents from pennies, nickels, dimes, and quarters (i.e., one cent, five cent, ten cent, and twenty five cent pieces). Find the generating function of $m_n.$

Click for Answer

The sequence $m_n$ is the counting sequence of the combinatorial class $\mathcal{M}$ consisting of tuples $(a,b,c,d) \in \mathbb{N}^4$ where the size of a tuple is $|(a,b,c,d)| = a+5b+10c+25d.$ The generating function of this class is $$ \begin{aligned} M(z) &= \sum_{(a,b,c,d)\in\mathbb{N}^4}z^{a+5b+10c+25d} \\[+4mm] &= \left(\sum_{a\geq 0}z^a\right)\left(\sum_{b\geq 0}z^{5b}\right)\left(\sum_{c\geq 0}z^{10c}\right)\left(\sum_{d\geq 0}z^{25d}\right) \\[+4mm] &= \frac{1}{(1-z)(1-z^5)(1-z^{10})(1-z^{25})}. \end{aligned} $$ This product is not very convenient for extracting coefficients, however a computer algebra system can easy generate many series terms. For instance, running

(1/(1-x)/(1-x^5)/(1-x^(10))/(1-x^(25))).series(x,101)

in Sage immediately gives the first 100 terms

1 + 1*x + 1*x^2 + 1*x^3 + 1*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + 2*x^9 + 4*x^10 + 4*x^11 + 4*x^12 + 4*x^13 + 4*x^14 + 6*x^15 + 6*x^16 + 6*x^17 + 6*x^18 + 6*x^19 + 9*x^20 + 9*x^21 + 9*x^22 + 9*x^23 + 9*x^24 + 13*x^25 + 13*x^26 + 13*x^27 + 13*x^28 + 13*x^29 + 18*x^30 + 18*x^31 + 18*x^32 + 18*x^33 + 18*x^34 + 24*x^35 + 24*x^36 + 24*x^37 + 24*x^38 + 24*x^39 + 31*x^40 + 31*x^41 + 31*x^42 + 31*x^43 + 31*x^44 + 39*x^45 + 39*x^46 + 39*x^47 + 39*x^48 + 39*x^49 + 49*x^50 + 49*x^51 + 49*x^52 + 49*x^53 + 49*x^54 + 60*x^55 + 60*x^56 + 60*x^57 + 60*x^58 + 60*x^59 + 73*x^60 + 73*x^61 + 73*x^62 + 73*x^63 + 73*x^64 + 87*x^65 + 87*x^66 + 87*x^67 + 87*x^68 + 87*x^69 + 103*x^70 + 103*x^71 + 103*x^72 + 103*x^73 + 103*x^74 + 121*x^75 + 121*x^76 + 121*x^77 + 121*x^78 + 121*x^79 + 141*x^80 + 141*x^81 + 141*x^82 + 141*x^83 + 141*x^84 + 163*x^85 + 163*x^86 + 163*x^87 + 163*x^88 + 163*x^89 + 187*x^90 + 187*x^91 + 187*x^92 + 187*x^93 + 187*x^94 + 213*x^95 + 213*x^96 + 213*x^97 + 213*x^98 + 213*x^99 + 242*x^100 + Order(x^101)

of the series expansion. In particular, the term 242*x^100 shows that there are 242 ways to make change for a dollar using pennies, nickles, dimes, and quarters.

In Part 4 of these notes we will see ways to use this rational generating function to create an extremely efficient algorithm for computing the terms $m_n,$ and derive the asymptotic behaviour $m_n \sim \frac{n^3}{7500}.$

Example: (a) Let $\mathcal{S}$ and $\mathcal{T}$ be finite sets of positive integers and define $$S(z)=\sum_{s \in \mathcal{S}}z^s \;\;\;\;\;\;\;\;\; T(z)=\sum_{t \in \mathcal{T}}z^t. $$ Show that the generating function for the combinatorial class of pairs $(s,t) \in \mathcal{S} \times \mathcal{T}$ with size function $|(s,t)|=s+t$ is $S(z)T(z).$

(b) Use part (a) to construct two distinct six-sided dice such that each die has a positive integer number of dots on each face and for any $n$ the probability that $n$ dots appear when rolling the two dice equals the probability that $n$ appears when rolling two standard dice (whose faces have $1,2,\dots,6$ dots).

Click for Answer

(a) The generating function for the class of pairs is $$ \sum_{(s,t) \in \mathcal{S} \times \mathcal{T}} z^{s+t} = \left(\sum_{s \in \mathcal{S}} z^s\right)\left(\sum_{t \in \mathcal{T}} z^t\right) = S(z)T(z). $$

(b) By part (a), the generating function for the sequence $c_n$ counting the number of ways to roll $n$ using two standard dice is $D(z) = (z+z^2+\cdots+z^6)^2.$ If we can factor $D(z)$ into two distinct polynomials $A(z)$ and $B(z)$ with no constant terms and positive integer coefficients that add to six then the exponents of these polynomials will define the faces of the distinct die we seek (where a coefficient greater than one means the corresponding exponent will appear on multiple faces). Conversely, any suitable pair of dice corresponds to such a factorization.

Consider the complete factorization (over the real numbers) $$ D(z) = z^2(z + 1)^2(z^2 + z + 1)^2(z^2 - z + 1)^2. $$ Since $A$ and $B$ have no constant terms then each must have a factor of $z.$ The factors $z + 1, z^2 + z + 1,$ and $z^2-z+1$ evaluate to $2,3,$ and $1$ when $z=1,$ respectively. Thus, since $A(1)=B(1)=6,$ we know that both $A$ and $B$ must contain one factor of $z+1$ and one factor of $z^2+z^2+1.$

Giving both $A$ and $B$ one factor of $z^2 - z + 1$ makes $A(z)=B(z)$ and characterizes two standard die. Because we want $A$ and $B$ to be distinct, we give both factors of $z^2 - z + 1$ to $B,$ say, giving $$ \begin{aligned} A(z) &= z(z + 1)(z^2 + z + 1) \\[+2mm] &= z + 2z^2 + 2z^3 + z^4, \\[+4mm] B(z) &= z(z + 1)(z^2 + z + 1)(z^2 - z + 1)^2 \\[+2mm] &= z+z^3+z^4+z^5+z^6+z^8. \end{aligned} $$ In particular, we can read off that one of the distinct dice should have faces $(1,2,2,3,3,4)$ and the other should have faces $(1,3,4,5,6,8).$ This set of dice are known as Sicherman dice, and our argument also shows that they are the only pair of six-sided dice with positive integer faces that have the same distribution as a pair of standard six-sided dice.

These examples illustrate how generating series, by providing an algebraic framework for sequences, allow us to use tools from pure mathematics (like polynomial factorization) to determine properties of discrete structures (like equivalence between pairs of dice). Modern methods in enumerative combinatorics borrow techniques from a stunning variety of mathematical domains, including real and complex analysis, algebraic and differential geometry, computational algebra, representation theory, harmonic and functional analysis, and topology.

Exercise: Let $t$ be a positive integer. Prove that $$ \sum_{n \geq 0} \binom{n+t-1}{t-1}z^n = \frac{1}{(1-z)^t} $$ by writing the left-hand side as the generating series for the number of multisets of size $n$ with $t$ types. Conclude by the generalized binomial theorem that $$ \binom{-t}{n} = (-1)^n\binom{n+t-1}{t-1}. $$ This identity is sometimes called the negative binomial theorem.

Formal Power Series as a Metric Space #

After studying the algebraic structure of formal power series in the last section, we now examine them as elements in a metric space.

Consider a sequence $F_0(z), F_1(z), F_2(z),\dots$ of formal power series in $R[[z]].$ We say this sequence formally converges if for every $n \in \mathbb{N}$ there exists some $L \in \mathbb{N}$ and $c_n \in R$ such that all coefficients $[z^n]F_k(z) = c_n$ whenever $k \geq L.$ In other words, a sequence of formal power series formally converges if for each $n$ the coefficient of $z^n$ eventually stabilizes to a fixed value. When this holds we write $$ \lim_{k \rightarrow\infty} F_k(z) = \sum_{n \geq 0} c_nz^n. $$

Examples: Consider the following sequences in $\mathbb{Q}[[z]].$

• If $F_k(z) = 2^kz^k$ then the sequence $(F_k)$ converges to $0$ since $[z^n]F_k(z) = 0$ whenever $k>n.$

• If $F_k(z) = 1 + z + \cdots + z^k$ then $$\lim_{k\rightarrow\infty} F_k(z) = \sum_{n \geq 0}z^n = \frac{1}{1-z}.$$

• If $F_0(z)=1$ and $F_k(z) = \frac{1}{1-z/k}$ for $k \geq 1$ then $(F_k)$ does not converge as, for instance, the coefficient $[z]F_k(z) = 1/k$ never stabilizes.

Caution: Make sure you understand the difference between a sequence of formal power series formally converging and the notion of convergence for sequences of real or complex functions.

The valuation $\text{val}(F)$ of a formal power series $F(z) = \sum_{n \geq 0} f_n z^n$ is the smallest natural number $i$ such that $f_i \neq 0.$

Example: A series whose expansion begins $3z^{\mathbf{2}}-11z^3+\cdots$ has valuation 2.

Exercise: Let $d:R[[z]]\times R[[z]] \rightarrow \mathbb{R}$ be the map that takes two formal power series $$F(z) = \sum_{n \geq 0} f_n z^n \;\;\;\;\;\;\;\;G(z) = \sum_{n \geq 0} g_n z^n$$ and returns $$ d(F,G) = 2^{-\text{val}(F-G)} = 2^{-\min \{i:f_i \neq g_i\}}. $$ Prove that for all $F,G,H \in R[[z]]$

• $d(F,G) \geq 0,$

• $d(F,G) = 0$ if and only if $F(z)=G(z),$

• $d(F,G) = d(G,F),$

• $d(F,H) \leq \max \left[ d(F,G) \;,\; d(G,H) \right].$

Exercise: Prove that a sequence $A_k(z)$ in $R[[z]]$ formally converges to some $A(z) \in R[[z]]$ if and only if $d(A_k,A)\rightarrow0$ as $k\rightarrow\infty.$

Exercise: Prove that if $A_k(z)$ is a sequence in $R[[z]]$ and for every $\epsilon>0$ there exists some $N \in \mathbb{N}$ such that $d(F_n,F_m) < \epsilon$ whenever $n,m \geq N$ then $A_k$ formally converges to a formal power series.

These exercises jointly imply that we can interpret $R[[z]]$ as a complete non-Archimedian metric space. Although we don’t use this interpretation directly in our study of formal power series, the fact that it exists both helps motivate our definitions and shows that much of what we develop can be generalized to other structures.

We now turn to infinite summation of formal power series, which is necessary to discuss the important operation of power series composition. We say that a sequence $(F_k)$ of formal power series is formally summable if the sequence $(S_N)$ defined by the partial sums $$ S_N = \sum_{k = 0}^N F_k(z) $$ formally converges. When $(F_k)$ is formally summable then we define $$ \sum_{k \geq 0} F_k(z) = \lim_{N \rightarrow \infty} \left(\sum_{k = 0}^N F_k(z)\right).$$ If $A,B \in R[[z]]$ then we define the composition $A(B(z))$ by $$ A(B(z)) = \sum_{n \geq 0} a_nB(z)^n$$ when the right-hand side exists. Although these definitions might seem abstract, there is an easy test to determine when the composition of two formal power series exists.

Theorem: Let $A,B \in R[[z]].$ If $A$ has only a finite number of non-zero coefficients then $A(B(z))$ always exists. If $A(z)$ has an infinite number of non-zero coefficients then $A(B(z))$ exists if and only if $B(0)=0$ ($B$ has no constant term).

Example: Use the series expansion $\frac{1}{1-z} = 1 + z + z^2 + \cdots$ and series composition to find an expansion of $\frac{1}{2-z-z^2}$ in $\mathbb{Q}[[z]].$

Click for Answer

Because the series $z/2+z^2/2$ has no constant term we can compose it inside the series for $1/(1-z)$ to conclude $$ \begin{aligned} \frac{1}{2-z-z^2} &= \frac{1}{2} \cdot \frac{1}{1-\left(\frac{z+z^2}{2}\right)} \\[+4mm] &= \frac{1}{2}\sum_{n \geq 0} \left(\frac{z+z^2}{2}\right)^n \\[+4mm] &= \frac{1}{2}\sum_{n \geq 0} 2^{-n}z^n\left(1+z\right)^n\\[+4mm] &= \sum_{n \geq 0} 2^{-n-1} \left(\sum_{k=0}^n \binom{n}{k}z^{n+k}\right) &&\text{(Binomial Theorem)}\\[+4mm] &= \sum_{\ell \geq 0} \left(\sum_{n=0}^\ell 2^{-n-1} \binom{n}{\ell-n}\right) z^{\ell} &&\text{(Set $n+k=\ell$)} \end{aligned} $$ Note that $\binom{n}{\ell-n}=0$ if $n < \ell/2.$

Calculus Operations and Exp / Log #

Let $F(z) = \sum_{n \geq 0} f_nz^n$ be an element of $R[[z]].$ The formal derivative of $F$ is defined as the formal power series $$ F^\prime(z) := \sum_{n \geq 0} nf_n z^{n-1} = \sum_{n \geq 0} (n+1)f_{n+1}z^n. $$ Similarly, if the positive integers have multiplicative inverses in $R$ (for instance, if $R$ is a field) then the formal integral of $F$ is defined as the formal power series $$ \int F(z) := \sum_{n \geq 0} \frac{f_n}{n+1} z^{n+1}. $$ These definitions are constructed to mirror how differentiation and integration works for (uniformly) convergent power series. As such, many of the normal rules of differentiation and integration from calculus continue to hold formally.

Commutation Rule: If a sequence $(F_k)$ of formal power series is formally summable then $$\left(\sum_{k \geq 0}F_k(z)\right)^\prime = \sum_{k \geq 0}F_k^\prime(z).$$

Product Rule: If $A(z)$ and $B(z)$ are formal power series then the formal derivative satisfies $$\left(A(z)B(z)\right)^\prime = A^\prime(z)B(z) + A(z)B^\prime(z).$$

Chain Rule: If $A(z)$ and $B(z)$ are formal power series and $B(0)=0$ then $$A(B(z))^\prime = A^\prime(B(z)) B^\prime(z).$$

Exercise: Prove the commutation, product, and chain rules.

If the positive integers have multiplicative inverses in $R$ then the formal exponential in $R[[z]]$ is defined to be the series $$\exp(z) = \sum_{n \geq 0}\frac{z^n}{n!}$$ while the formal logarithm is defined to be the series satisfying $$ \log(1+z) = \int \frac{1}{1+z} = \sum_{n \geq 1} \frac{(-1)^{n+1}}{n} z^n.$$

Exercise: Prove the following identities using only formal arguments. $$ \begin{aligned} \exp(z)^\prime &= \exp(z) \\[+2mm] \log(1+z)^\prime &= \frac{1}{1+z} \\[+2mm] \exp((a+b)z) &= \exp(az)\exp(bz) &&(a,b\in R) \\[+2mm] \exp(z)^{-1} &= \exp(-z) \\[+2mm] \log\left(A(z)B(z)\right) &= \log(A(z)) + \log(B(z)) &&\text{if $A(0)=B(0)=1$} \\[+2mm] \log(\exp(z)) &= z \\[+2mm] \exp(\log(1+z)) &= 1+z \end{aligned} $$ Hint: You may find the chain rule useful for the final identities.

In analogy to complex analysis, we use the formal exponential and logarithmic series to define general powers. In particular, if the positive integers are invertible in $R$ then we define $$ (1+z)^\alpha := \exp\left(\alpha \log(1+z) \right). $$

It can be shown that the generalized binomial theorem above can be further extended to $$ (1+z)^\alpha = \sum_{n \geq 0}\binom{\alpha}{n}z^n $$ in $\mathbb{C}[[z]]$ for any $\alpha \in \mathbb{C}.$ As a consequence, when $\alpha \in \mathbb{Q}$ then this definition of $(1+z)^{\alpha}$ agrees with our definition above.

As mentioned above, if a convergent series satisfies an algebraic equation then the formal series with the same coefficients also satisfies that equation. In fact, this is a reflection of a larger phenomenon.

Exercise: Prove that for any formal power series $F(z) \in \mathbb{C}[[z]]$ there exists a sequence of power series $F_k(z)$ that formally converge to $F(z)$ such that every $F_k(z)$ also defines a convergent series (in the calculus sense) for all $z \in \mathbb{C}.$

Click for Answer

Any formal power series $F(z) = \sum_{n \geq 0}f_nz^n$ is the formal limit of the partial sum sequence $F_k(z) = f_0 + f_1z + \cdots + f_kz^k.$ Since each $F_k$ is a polynomial, it converges for all $z \in \mathbb{C}.$

This exercise implies that the convergent power series are dense in the metric space of formal power series with complex coefficients. As a consequence, any identity for convergent power series that can be represented by a continuous operator on formal series (including one built from addition, multiplication, subtraction, division, differentiation, and integration) will continue to hold for all formal power series. Of course, we cannot use such an argument for formal series whose coefficients cannot be embedded inside the complex numbers, so formal arguments are still often needed.

Tips for Coefficient Extraction #

We end this chapter by summarizing some useful ideas for coefficient extraction.

• Addition $$[z^n]\left(A(z)+B(z)\right) = [z^n]A(z) + [z^n]B(z)$$

• Multiplication $$[z^n]\left(A(z)B(z)\right) = \sum_{k=0}^n [z^k]A(z) \cdot [z^{n-k}]B(z)$$

• Coefficient Scaling $$[z^n]F(\rho z) = \rho^n \; [z^n]F(z)$$

• Monomial Multiplication $$[z^n]z^kF(z) = \begin{cases} [z^{n-k}]F(z) &: k \leq n \\ 0 &: k > n \end{cases} $$

• Re-Indexing If $a,b \in \mathbb{N}$ with $b>a$ then $$\sum_{n=a}^b f_nz^n = \sum_{n=0}^{b-a} f_{n+a} z^{n+a}$$ (We can also take $b=\infty$ in which case both series have upper bound $\infty$)

• Binomial Theorem If $\alpha \in \mathbb{C}$ then $$(1+z)^\alpha = \sum_{n \geq 0}\binom{\alpha}{n}z^n$$

• Negative Binomial Theorem If $t$ is a positive integer and $n\in\mathbb{N}$ then $$\binom{-t}{n} = (-1)^n \binom{n+t-1}{t-1}$$

• Use of Convergent Series If $K$ is a field contained in the complex numbers and a convergent series with coefficients in $K$ is found to satisfy a polynomial equation (by the quadratic formula, Taylor series, etc.) then the formal series defined by these coefficients satisfies the same polynomial equation in $K[[z]].$

Example: Find $[z^n] \frac{1-\sqrt{1-4z}}{2z},$ where $\sqrt{1-4z} = (1-4z)^{1/2}$ and we note that this expression is a formal power series as the numerator has no constant term (so the power of $z$ in the denominator does not create a Laurent expansion).

Click for Answer

Using the formulas above, we have $$ \begin{aligned} [z^n] \frac{1-\sqrt{1-4z}}{2z} &= 2^{-1} [z^{n+1}]\left(1-\sqrt{1-4z}\right) \\[+4mm] &= - 2^{-1} [z^{n+1}](1-4z)^{1/2} \\[+4mm] &= -2^{-1}(-4)^{n+1} [z^{n+1}](1+z)^{1/2} \\[+4mm] &= -2^{-1}(-4)^{n+1} \cdot \frac{(1/2)(1/2-1) \cdots (1/2-n)}{(n+1)!} \\[+4mm] &= 2^{n} \cdot \frac{(-2)^n(1/2-1) \cdots (1/2-n)}{(n+1)!} \\[+4mm] &= 2^n \cdot \frac{(1)(1)(3)(5)\cdots(2n-1)}{(n+1)!} \cdot \frac{n!}{n!} \\[+4mm] &= \frac{(2n)!}{n!(n+1)!} \\[+4mm] &= \frac{1}{n+1}\binom{2n}{n}. \end{aligned} $$

Additional Problems #

Problem 1. (a) Determine the generating function $N(z)$ of the combinatorial class defined by the natural numbers $\mathbb{N}$ using the weight function $$ |n| = \begin{cases} \frac{3n}{2}+1 &\text{if $n$ is even} \\ n-1 & \text{if $n$ is odd.} \end{cases} $$ Express $N(z)$ as a rational function in $z.$

(b) Repeat part (a) with the new weight function $$ |n| = \begin{cases} n & \text{if $n \equiv 0 \mod 3$} \\ n+1 &\text{if $n \equiv 1 \mod 3$ } \\ n+2 &\text{if $n \equiv 2 \mod 3.$} \end{cases} $$

(c) Try to repeat part (a) with the new weight function $$ |n| = \begin{cases} n \mod 2 & \text{if $n$ is divisible by 3} \\ n+1 & \text{otherwise.} \end{cases} $$

Problem 2. Let $F(z)$ be the generating function of the sequence $(f_n).$ Find explicit expressions for the generating functions of the following sequences in terms of $F(z).$

(a) The sequence $$(s_n) = 0,f_1,0,f_3,0,f_5,\dots$$ containing the terms in $(f_n)$ with odd index.

(b) The sequence $$(s_n) = -f_0,f_1,-f_2,f_3,\dots$$ where every other term is negated.

(c) The sequence $(s_n)$ of partial sums $$s_n = \sum_{k=0}^n f_k$$ which begins $f_0,f_0+f_1,f_0+f_1+f_2,\dots.$

Problem 3. Which of the following expressions are well-defined formal power series compositions in $\mathbb{Q}[[z]],$ $$ \begin{aligned} \exp(z+1) \qquad \exp(\exp(z)&-1) \qquad \sum_{k \geq 1} \frac{z^k}{1-z^k} \\[+5mm] \sin(\cos(z)) \quad&\quad \cos(\sin(z)) \end{aligned} $$ where $$\sin(z) = \sum_{n \geq 0} \frac{(-1)^n}{(2n+1)!}z^{2n+1} \qquad \cos(z) = \sum_{n \geq 0} \frac{(-1)^n}{(2n)!}z^{2n}. $$

Problem 4. Find $[z^n] \frac{(1+z)^n}{1-z}$ when $n\in\mathbb{N}.$

Problem 5. Determine whether or not the sequence $$ F_k(z) = \left(1+\frac{z}{k}\right)^k $$ formally converges in $\mathbb{Q}[[z]]$ as $k\rightarrow\infty.$ If it does converge, determine its value.

Problem 6. Prove that a sequence $(F_k(z))$ of formal power series is formally summable if and only if for every $N \in \mathbb{N}$ the set of indices $k$ such that $\text{val}(F_k) \leq N$ is finite.

Problem 7. (a) Let $(F_k(z))$ be a sequence of formal power series. Show that the limit $$ \prod_{k\geq0} \left(1+F_k(z)\right) = \lim_{N \rightarrow\infty} \left(\prod_{k=0}^N \left(1+F_k(z)\right)\right) $$ exists if and only if $(F_k(z))$ is formally summable.

(b) Prove that $$\prod_{k \geq 0}\left(1 + z^{2^k}\right) = \sum_{n \geq 0}z^n.$$

Problem 8. Express the generating function for the number $t_n$ of subsets of $[n]=\{1,\dots,n\}$ whose size is divisible by 3 in terms of the generating function $F(z) = (1+z)^n$ for the number of subsets of $[n]$ with no restriction. Find a simple formula for $t_n.$

Problem 9. Let $P(z) = \sum_{n \geq 0} p_n z^n$ be the generating function for the probability $p_n$ that a randomly chosen class at the University of Waterloo has $n$ students.

(a) Prove that the series $P(z)$ converges at $z=1$ to the value $P(1)=1.$

(b) Assuming that $P^\prime(z)$ converges at $z=1,$ give a combinatorial interpretation of $P^\prime(1).$

(c) Assuming that $P^\prime(z)$ converges at $z=1,$ give a combinatorial interpretation to the coefficients of $zP^\prime(z)/P^\prime(1).$

Problem 10. The combinatorial class $\mathcal{P}$ of 123-partitions is the class whose objects are tuples $(a,b,c) \in \mathbb{N}^3$ with size function $|(a,b,c)|=a+2b+3c.$ Express the generating function $P(z)$ for the number $p_n$ of 123-partitions of size $n$ as a rational function, then use a partial fraction decomposition to give an explicit formula for $p_n.$

Problem 11. Let $F(z) = \sum_{n \geq 0} \binom{2n}{n}^{-1} z^n.$

(a) Use identities of binomial coefficients to prove that $F(z)$ satisfies the differential equation $$ z(z-4)F^\prime(z) + (z+2)F(z) - 2 = 0. $$

(b) Use a computer algebra system to solve this first-order differential equation with the initial conditions $F(0)=1$ and $F^\prime(0)=1/2.$ Prove that $$ \sum_{n \geq 0} \binom{2n}{n}^{-1} = \frac{2(18+\sqrt{3}\pi)}{27}. $$ (If you get stuck or don’t have access to a computer algebra system then you can click here to solve the ODE using Wolfram Alpha). See Chapter 11.3 of Pi and the AGM for a large number of generalizations on this problem.

Problem 12. Let $a_n$ be the number of alternating permutations $\pi=\pi_1 \cdots \pi_n$ satisfying $\pi_1 > \pi_2 < \pi_3 > \pi_4 < \dots$ when $n$ is odd, and $a_n=0$ when $n$ is even. Let $$ T(z) = \sum_{n \geq 0} \frac{a_n}{n!}z^n = \sum_{k \geq 0} \frac{a_{2k+1}}{(2k+1)!}z^{2k+1}. $$ (a) By considering the location of $1$ in a permutation, prove that for all $k \geq 1$ $$ a_{2k+1} = \sum_{\substack{1 \leq j \leq 2k \\[+1mm] j \text{ odd}}} \binom{2k}{j}a_ja_{2k-j}.$$

(b) Using this recurrence, show that $T^\prime(z) = T(z)^2 + 1.$

(c) Solve this differential equation to conclude that $T(z) = \tan z.$

Problem 13. Use the fact that $[z^n] \frac{z^k}{(1-z)^{k+1}}=\binom{n}{k}$ to show that for any formal power series $A(z),$ $$ [z^n] \frac{1}{1-z}A\left(\frac{z}{z-1}\right) = \sum_{k=0}^n (-1)^k \binom{n}{k}[z^k] A(z) $$ for all $n\geq 0.$

Appendix: Convergent Series #

In this appendix we recap standard information about convergent infinite series.

Remark: For reasons that will become clear later, it is most natural to work with convergent series over the complex numbers $\mathbb{C}.$ A reader unfamiliar with complex numbers can still get the full intuition by imagining all series coefficients and constants are real numbers.

An infinite series $\sum_{k\geq0} a_k$ of numbers $a_k \in \mathbb{C}$ is said to converge to the value $S\in\mathbb{C}$ if the sequence $(S_N)$ of partial sums $$ S_N = \sum_{k=0}^N a_k $$ satisfies $\displaystyle\lim_{N\rightarrow\infty} S_N = S.$ If $z$ is a variable then the power series $$ f(z) = \sum_{k=0}^{\infty} c_kz^k $$ with coefficients $c_k \in \mathbb{C}$ converges to the value $f(a)=S$ at the point $a \in \mathbb{C}$ if the infinite series $\sum_{k\geq0} c_ka^k$ converges to $S.$

Example: The infinite series $\sum_{k \geq 0}z^k$ converges at $z=1/2$ to the value $$ \lim_{N\rightarrow\infty} \left(\sum_{k=0}^N 2^{-k}\right) = \lim_{N\rightarrow\infty} \left(2 - 2^{-N}\right) = 2. $$

The following results are usually discussed in a first calculus course.

Ratio Test: Suppose the limit $R = \displaystyle\lim_{n\rightarrow\infty}\left|\frac{c_{n+1}}{c_n}\right|$ exists, including the possibility that $R=\infty.$ If $R>0$ is finite then the infinite series $$ f(z) = \sum_{k=0}^{\infty} c_kz^k $$ converges whenever $|z|<1/R$ and does not converge when $|z|>R.$ If $R=0$ then $f(z)$ converges for all $z \in \mathbb{C},$ while if $R=\infty$ then $f(z)$ only converges when $z=0.$

Root Test: The same conclusions in the Ratio Test hold if $R = \displaystyle\lim_{n\rightarrow\infty}|c_n|^{1/n}.$

Example: If $a>0$ is a positive real number then the sequence $c_n = a^n$ satisfies $\displaystyle\lim_{n\rightarrow\infty}|c_n|^{1/n} = a,$ so $\sum_{k \geq 0} a^nz^n$ converges when $|z|<1/a.$ In fact, $$ \sum_{k \geq 0} a^nz^n = \frac{1}{1-az} $$ whenever $|z|<1/a.$