Combinatorics and Algebra: Formal Power Series and an Introduction to Algebraic Combinatorics

We examine the algebraic structure of the formal power series ring Q[[x]], including multiplicative inverses, composition, and formal differentiation. We then discuss P-recursive (holonomic) sequences, prove the Lagrange inversion formula, and introduce the WZ method and hypergeometric series.

Folio Official

March 1, 2026

1 The Ring of Formal Power Series

Definition 1 (Formal power series ring).

The ring of formal power series

Q [[x]]

over

Q

consists of all expressions of the form

f (x) = n = 0 \sum \infty a_{n} x^{n} (a_{n} \in Q),

equipped with coefficientwise addition and convolution (Cauchy product) as multiplication.

Theorem 2.

Q [[x]]

is an integral domain. That is, if

f (x) \neq = 0

and

g (x) \neq = 0

, then

f (x) g (x) \neq = 0

Proof.

Write

f (x) = \sum a_{n} x^{n}

and

g (x) = \sum b_{n} x^{n}

. Let

p

and

q

be the smallest indices with

a_{p} \neq = 0

and

b_{q} \neq = 0

, respectively. The coefficient of

x^{p + q}

f (x) g (x)

\sum_{k = 0}^{p + q} a_{k} b_{p + q - k}

. When

k < p

we have

a_{k} = 0

, and when

k > p

we have

p + q - k < q

b_{p + q - k} = 0

. The only surviving term is

a_{p} b_{q} \neq = 0

. □

2 Multiplicative Inverses

Theorem 3.

A formal power series

f (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} \in Q [[x]]

has a multiplicative inverse if and only if

a_{0} \neq = 0

Proof.

(\Rightarrow)

f (x) g (x) = 1

, then the product of the constant terms must be

1

, so

a_{0} \neq = 0

(\Leftarrow)

We construct

g (x) = \sum b_{n} x^{n}

satisfying

f (x) g (x) = 1

. Set

b_{0} = 1/ a_{0}

. For

n \geq 1

, the equation

\sum_{k = 0}^{n} a_{k} b_{n - k} = 0

gives

b_{n} = - \frac{1}{a _{0}} k = 1 \sum n a_{k} b_{n - k},

which determines each

b_{n}

uniquely by induction. □

3 Composition

Definition 4 (Composition).

For

f (x) = \sum a_{n} x^{n}

and

g (x) = \sum_{n \geq 1} b_{n} x^{n}

(where

g

has zero constant term), the composition

f (g (x)) = \sum_{n = 0}^{\infty} a_{n} g (x)^{n}

is a well-defined element of

Q [[x]]

Theorem 5.

A formal power series

g (x) = \sum_{n \geq 1} b_{n} x^{n}

has a compositional inverse

\overset{g}{ˉ}

(satisfying

g (\overset{g}{ˉ} (x)) = \overset{g}{ˉ} (g (x)) = x

) if and only if

b_{1} \neq = 0

Proof.

Write

\overset{g}{ˉ} (x) = \sum c_{n} x^{n}

with

c_{0} = 0

. Comparing the coefficient of

x

g (\overset{g}{ˉ} (x)) = x

gives

b_{1} c_{1} = 1

, so

c_{1} = 1/ b_{1}

(requiring

b_{1} \neq = 0

). The higher-order coefficients are then uniquely determined by successive comparison of coefficients. □

4 Formal Differentiation

Definition 6 (Formal derivative).

The formal derivative is defined by

D (n = 0 \sum \infty a_{n} x^{n}) = n = 1 \sum \infty n a_{n} x^{n - 1} .

The operator

D

is a derivation on

Q [[x]]

: it satisfies

D (f g) = D (f) g + f D (g)

5 P-recursive Sequences

Definition 7 (P-recursive (holonomic) sequence).

A sequence

(a_{n})

is P-recursive (or holonomic) if there exist polynomials

p_{0} (n), p_{1} (n), \dots, p_{d} (n)

n

(with

p_{d}

not identically zero) such that

p_{d} (n) a_{n + d} + p_{d - 1} (n) a_{n + d - 1} + \dots + p_{0} (n) a_{n} = 0

for all sufficiently large

n

Example 8.

The sequence

a_{n} = n!

satisfies

a_{n + 1} = (n + 1) a_{n}

, i.e.,

a_{n + 1} - (n + 1) a_{n} = 0

, so it is P-recursive. The central binomial coefficients

a_{n} = (n 2 n)

are also P-recursive, satisfying

(n + 1) a_{n + 1} = 2 (2 n + 1) a_{n}

Remark 9.

The generating function of a P-recursive sequence satisfies a linear ODE with polynomial coefficients; such a series is called D-finite. The class of P-recursive sequences is closed under addition, Hadamard (termwise) product, and convolution. A great many sequences arising in combinatorics belong to this class.

6 The Lagrange Inversion Formula

Theorem 10 (Lagrange inversion formula).

Let

ϕ (x) \in Q [[x]]

with

ϕ (0) \neq = 0

. Then the equation

f (x) = x ϕ (f (x))

has a unique solution

f (x) \in Q [[x]]

with

f (0) = 0

, and its coefficients are given by

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] ϕ (y)^{n} .

More generally, for any

h (x) \in Q [[x]]

[x^{n}] h (f (x)) = \frac{1}{n} [y^{n - 1}] h^{'} (y) ϕ (y)^{n} .

Proof.

From

f (x) = x ϕ (f (x))

we obtain

x = f / ϕ (f)

. Treating

g = f

as a new variable, we have

x (g) = g / ϕ (g)

, and

[x^{n}] h (f (x))

can be computed by an appropriate change of variables.

More formally,

[x^{n}] h (f) = \frac{1}{n} [x^{n - 1}] h^{'} (x) ϕ (x)^{n}

, which can be established by a residue-like calculation. We write

[x^{n}] h (f) = \frac{1}{2 πi} \oint h (f (x)) x^{- n - 1} d x

and substitute

x = g / ϕ (g)

, so

d x = (ϕ (g) - g ϕ^{'} (g)) / ϕ (g)^{2} d g

. Simplifying yields the desired identity. (Within the framework of formal power series, a direct coefficient-comparison proof is also possible.) □

Example 11.

For the Catalan numbers: set

f (x) = x (1 + f (x))^{2}

, i.e.,

ϕ (y) = (1 + y)^{2}

. Then

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] (1 + y)^{2 n} = \frac{1}{n} (n - 1 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n}

7 The WZ Method and Hypergeometric Series

Definition 12 (Hypergeometric term).

A sequence

(t_{k})

is a hypergeometric term if

t_{k + 1} / t_{k}

is a rational function of

k

Definition 13 (Hypergeometric series).

The hypergeometric series is

_{p} F_{q} (a_{1}, \dots, a_{p} b_{1}, \dots, b_{q}; x) = k = 0 \sum \infty \frac{( a _{1} ) _{k} \dots ( a _{p} ) _{k}}{( b _{1} ) _{k} \dots ( b _{q} ) _{k}} \frac{x ^{k}}{k !},

where

(a)_{k} = a (a + 1) \dots (a + k - 1)

is the Pochhammer symbol (rising factorial).

Theorem 14 (Principle of the WZ method (Wilf–Zeilberger, 1990)).

To prove an identity

\sum_{k} F (n, k) = c

(a constant independent of

n

), it suffices to find a rational function

R (n, k)

— the WZ proof certificate— such that

G (n, k) = R (n, k) F (n, k)

satisfies

F (n + 1, k) - F (n, k) = G (n, k + 1) - G (n, k) .

Summing over

k

, the right-hand side telescopes to

0

, yielding

\sum_{k} F (n + 1, k) = \sum_{k} F (n, k)

Remark 15.

Gosper's algorithm determines algorithmically whether a given hypergeometric term has a closed-form indefinite sum, and can verify the existence of a WZ pair. Zeilberger's algorithm (creative telescoping) automatically discovers a recurrence satisfied by a hypergeometric sum. These methods form the foundation for computer-algebraic proof of combinatorial identities.

Example 16.

The Vandermonde convolution

\sum_{k = 0}^{r} (k m) (r - k n) = (r m + n)

is a special case of the Chu–Vandermonde identity

_{2} F_{1} (- m, - r; n - r + 1; 1) = (r m + n) / (r n)

and can be proved mechanically by the WZ method.

Combinatorics Discrete Mathematics Textbook Formal Power Series Algebraic Combinatorics

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Combinatorics and Algebra: Formal Power Series and an Introduction to Algebraic Combinatorics

Folio Official

March 1, 2026

1 The Ring of Formal Power Series

Definition 1 (Formal power series ring).

The ring of formal power series

Q [[x]]

over

Q

consists of all expressions of the form

f (x) = n = 0 \sum \infty a_{n} x^{n} (a_{n} \in Q),

equipped with coefficientwise addition and convolution (Cauchy product) as multiplication.

Theorem 2.

Q [[x]]

is an integral domain. That is, if

f (x) \neq = 0

and

g (x) \neq = 0

, then

f (x) g (x) \neq = 0

Proof.

Write

f (x) = \sum a_{n} x^{n}

and

g (x) = \sum b_{n} x^{n}

. Let

p

and

q

be the smallest indices with

a_{p} \neq = 0

and

b_{q} \neq = 0

, respectively. The coefficient of

x^{p + q}

f (x) g (x)

\sum_{k = 0}^{p + q} a_{k} b_{p + q - k}

. When

k < p

we have

a_{k} = 0

, and when

k > p

we have

p + q - k < q

b_{p + q - k} = 0

. The only surviving term is

a_{p} b_{q} \neq = 0

. □

2 Multiplicative Inverses

Theorem 3.

A formal power series

f (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} \in Q [[x]]

has a multiplicative inverse if and only if

a_{0} \neq = 0

Proof.

(\Rightarrow)

f (x) g (x) = 1

, then the product of the constant terms must be

1

, so

a_{0} \neq = 0

(\Leftarrow)

We construct

g (x) = \sum b_{n} x^{n}

satisfying

f (x) g (x) = 1

. Set

b_{0} = 1/ a_{0}

. For

n \geq 1

, the equation

\sum_{k = 0}^{n} a_{k} b_{n - k} = 0

gives

b_{n} = - \frac{1}{a _{0}} k = 1 \sum n a_{k} b_{n - k},

which determines each

b_{n}

uniquely by induction. □

3 Composition

Definition 4 (Composition).

For

f (x) = \sum a_{n} x^{n}

and

g (x) = \sum_{n \geq 1} b_{n} x^{n}

(where

g

has zero constant term), the composition

f (g (x)) = \sum_{n = 0}^{\infty} a_{n} g (x)^{n}

is a well-defined element of

Q [[x]]

Theorem 5.

A formal power series

g (x) = \sum_{n \geq 1} b_{n} x^{n}

has a compositional inverse

\overset{g}{ˉ}

(satisfying

g (\overset{g}{ˉ} (x)) = \overset{g}{ˉ} (g (x)) = x

) if and only if

b_{1} \neq = 0

Proof.

Write

\overset{g}{ˉ} (x) = \sum c_{n} x^{n}

with

c_{0} = 0

. Comparing the coefficient of

x

g (\overset{g}{ˉ} (x)) = x

gives

b_{1} c_{1} = 1

, so

c_{1} = 1/ b_{1}

(requiring

b_{1} \neq = 0

). The higher-order coefficients are then uniquely determined by successive comparison of coefficients. □

4 Formal Differentiation

Definition 6 (Formal derivative).

The formal derivative is defined by

D (n = 0 \sum \infty a_{n} x^{n}) = n = 1 \sum \infty n a_{n} x^{n - 1} .

The operator

D

is a derivation on

Q [[x]]

: it satisfies

D (f g) = D (f) g + f D (g)

5 P-recursive Sequences

Definition 7 (P-recursive (holonomic) sequence).

A sequence

(a_{n})

is P-recursive (or holonomic) if there exist polynomials

p_{0} (n), p_{1} (n), \dots, p_{d} (n)

n

(with

p_{d}

not identically zero) such that

p_{d} (n) a_{n + d} + p_{d - 1} (n) a_{n + d - 1} + \dots + p_{0} (n) a_{n} = 0

for all sufficiently large

n

Example 8.

The sequence

a_{n} = n!

satisfies

a_{n + 1} = (n + 1) a_{n}

, i.e.,

a_{n + 1} - (n + 1) a_{n} = 0

, so it is P-recursive. The central binomial coefficients

a_{n} = (n 2 n)

are also P-recursive, satisfying

(n + 1) a_{n + 1} = 2 (2 n + 1) a_{n}

Remark 9.

6 The Lagrange Inversion Formula

Theorem 10 (Lagrange inversion formula).

Let

ϕ (x) \in Q [[x]]

with

ϕ (0) \neq = 0

. Then the equation

f (x) = x ϕ (f (x))

has a unique solution

f (x) \in Q [[x]]

with

f (0) = 0

, and its coefficients are given by

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] ϕ (y)^{n} .

More generally, for any

h (x) \in Q [[x]]

[x^{n}] h (f (x)) = \frac{1}{n} [y^{n - 1}] h^{'} (y) ϕ (y)^{n} .

Proof.

From

f (x) = x ϕ (f (x))

we obtain

x = f / ϕ (f)

. Treating

g = f

as a new variable, we have

x (g) = g / ϕ (g)

, and

[x^{n}] h (f (x))

can be computed by an appropriate change of variables.

More formally,

[x^{n}] h (f) = \frac{1}{n} [x^{n - 1}] h^{'} (x) ϕ (x)^{n}

, which can be established by a residue-like calculation. We write

[x^{n}] h (f) = \frac{1}{2 πi} \oint h (f (x)) x^{- n - 1} d x

and substitute

x = g / ϕ (g)

, so

d x = (ϕ (g) - g ϕ^{'} (g)) / ϕ (g)^{2} d g

. Simplifying yields the desired identity. (Within the framework of formal power series, a direct coefficient-comparison proof is also possible.) □

Example 11.

For the Catalan numbers: set

f (x) = x (1 + f (x))^{2}

, i.e.,

ϕ (y) = (1 + y)^{2}

. Then

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] (1 + y)^{2 n} = \frac{1}{n} (n - 1 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n}

7 The WZ Method and Hypergeometric Series

Definition 12 (Hypergeometric term).

A sequence

(t_{k})

is a hypergeometric term if

t_{k + 1} / t_{k}

is a rational function of

k

Definition 13 (Hypergeometric series).

The hypergeometric series is

_{p} F_{q} (a_{1}, \dots, a_{p} b_{1}, \dots, b_{q}; x) = k = 0 \sum \infty \frac{( a _{1} ) _{k} \dots ( a _{p} ) _{k}}{( b _{1} ) _{k} \dots ( b _{q} ) _{k}} \frac{x ^{k}}{k !},

where

(a)_{k} = a (a + 1) \dots (a + k - 1)

is the Pochhammer symbol (rising factorial).

Theorem 14 (Principle of the WZ method (Wilf–Zeilberger, 1990)).

To prove an identity

\sum_{k} F (n, k) = c

(a constant independent of

n

), it suffices to find a rational function

R (n, k)

— the WZ proof certificate— such that

G (n, k) = R (n, k) F (n, k)

satisfies

F (n + 1, k) - F (n, k) = G (n, k + 1) - G (n, k) .

Summing over

k

, the right-hand side telescopes to

0

, yielding

\sum_{k} F (n + 1, k) = \sum_{k} F (n, k)

Remark 15.

Example 16.

The Vandermonde convolution

\sum_{k = 0}^{r} (k m) (r - k n) = (r m + n)

is a special case of the Chu–Vandermonde identity

_{2} F_{1} (- m, - r; n - r + 1; 1) = (r m + n) / (r n)

and can be proved mechanically by the WZ method.

Combinatorics Discrete Mathematics Textbook Formal Power Series Algebraic Combinatorics

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Combinatorics and Algebra: Formal Power Series and an Introduction to Algebraic Combinatorics

1 The Ring of Formal Power Series

2 Multiplicative Inverses

3 Composition

4 Formal Differentiation

5 P-recursive Sequences

6 The Lagrange Inversion Formula

7 The WZ Method and Hypergeometric Series

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Combinatorics and Algebra: Formal Power Series and an Introduction to Algebraic Combinatorics

1 The Ring of Formal Power Series

2 Multiplicative Inverses

3 Composition

4 Formal Differentiation

5 P-recursive Sequences

6 The Lagrange Inversion Formula

7 The WZ Method and Hypergeometric Series

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry