Generating Functions I (Ordinary): Encoding Sequences as Power Series

We introduce ordinary generating functions (OGFs), establish the connection between products and convolutions, derive Binet's formula for the Fibonacci numbers via OGFs, and present the generating functions for the Catalan numbers and the partition function.

Folio Official

March 1, 2026

1 Definition of Ordinary Generating Functions

Definition 1 (Ordinary generating function).

Given a sequence

(a_{n})_{n \geq 0}

, the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n}

is called the ordinary generating function (OGF) of

(a_{n})

Remark 2.

Generating functions are treated as "formal" power series — we do not need to substitute a specific value for

x

or worry about convergence. What matters is the algebraic manipulation of coefficients. That said, analytic arguments are sometimes employed to derive explicit formulas.

Example 3.

The OGF of the constant sequence

a_{n} = 1

(

n \geq 0

) is

\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}

. The OGF of

a_{n} = n

\sum_{n = 0}^{\infty} n x^{n} = \frac{x}{( 1 - x ) ^{2}}

2 Products and Convolution

Theorem 4.

Let

A (x)

and

B (x)

be the OGFs of sequences

(a_{n})

and

(b_{n})

, respectively. The coefficient

c_{n}

of the product

C (x) = A (x) B (x)

is given by

c_{n} = k = 0 \sum n a_{k} b_{n - k} .

This is called the convolution of

(a_{n})

and

(b_{n})

Proof.

This is immediate from the definition of the product of formal power series:

A (x) B (x) = \sum_{n} (\sum_{k = 0}^{n} a_{k} b_{n - k}) x^{n}

. □

3 Fibonacci Numbers and Binet's Formula

Definition 5 (Fibonacci sequence).

The Fibonacci sequence is defined by

F_{0} = 0

F_{1} = 1

, and

F_{n} = F_{n - 1} + F_{n - 2}

for

n \geq 2

Theorem 6 (Binet's formula).

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

where

φ = \frac{1 + 5}{2}

and

ψ = \frac{1 - 5}{2}

Proof.

Set

F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}

. Multiplying the recurrence

F_{n} = F_{n - 1} + F_{n - 2}

x^{n}

and summing over

n \geq 2

yields

F (x) - F_{1} x - F_{0} = x (F (x) - F_{0}) + x^{2} F (x) .

Solving for

F (x)

gives

F (x) (1 - x - x^{2}) = x

, whence

F (x) = \frac{x}{1 - x - x ^{2}}

We now perform a partial fraction decomposition. Since

1 - x - x^{2} = - (x - (- φ^{- 1})) (x - (- ψ^{- 1}))

, we obtain

F (x) = \frac{1}{5} (\frac{1}{1 - φ x} - \frac{1}{1 - ψ x}) .

Expanding

\frac{1}{1 - αx} = \sum_{n = 0}^{\infty} α^{n} x^{n}

and reading off the coefficient of

x^{n}

gives

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

. □

4 The Generating Function for the Catalan Numbers

Definition 7 (Catalan number).

The

n

-th Catalan number is

C_{n} = \frac{1}{n + 1} (n 2 n)

for

n \geq 0

Theorem 8.

The OGF

C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}

of the Catalan numbers is

C (x) = \frac{1 - 1 - 4 x}{2 x} .

Proof.

The Catalan numbers satisfy the recurrence

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

for

n \geq 1

, with

C_{0} = 1

. In terms of the OGF, this translates to

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

. Solving the quadratic

x C^{2} - C + 1 = 0

yields

C (x) = \frac{1 \pm 1 - 4 x}{2 x}

. The initial condition

C (0) = C_{0} = 1

forces us to take the minus sign. □

5 The Generating Function for the Partition Numbers

Definition 9 (Partition number).

The number of ways to write a nonneg\/ative integer

n

as a sum of positive integers, disregarding order, is called the partition number

p (n)

Theorem 10 (Euler's generating function for the partition numbers).

n = 0 \sum \infty p (n) x^{n} = k = 1 \prod \infty \frac{1}{1 - x ^{k}}

Proof.

For each positive integer

k

, using

k

exactly

j

times in a partition corresponds to the monomial

x^{kj}

. The generating function for the number of times

k

can be used is

\frac{1}{1 - x ^{k}} = j = 0 \sum \infty x^{kj} .

Taking the product over all

k \geq 1

, the coefficient of

x^{n}

in the resulting product counts the number of ways to partition

n

into positive integer parts, which is

p (n)

. □

Remark 11.

A recurrence for the partition numbers can be derived from Euler's pentagonal number theorem:

\prod_{k = 1}^{\infty} (1 - x^{k}) = \sum_{m = - \infty}^{\infty} (- 1)^{m} x^{m (3 m - 1) /2}

Combinatorics Discrete Mathematics Textbook Generating Functions OGF

Folio Official

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

1 followers·107 articles

Generating Functions I (Ordinary): Encoding Sequences as Power Series

Folio Official

March 1, 2026

1 Definition of Ordinary Generating Functions

Definition 1 (Ordinary generating function).

Given a sequence

(a_{n})_{n \geq 0}

, the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n}

is called the ordinary generating function (OGF) of

(a_{n})

Remark 2.

Generating functions are treated as "formal" power series — we do not need to substitute a specific value for

x

or worry about convergence. What matters is the algebraic manipulation of coefficients. That said, analytic arguments are sometimes employed to derive explicit formulas.

Example 3.

The OGF of the constant sequence

a_{n} = 1

(

n \geq 0

) is

\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}

. The OGF of

a_{n} = n

\sum_{n = 0}^{\infty} n x^{n} = \frac{x}{( 1 - x ) ^{2}}

2 Products and Convolution

Theorem 4.

Let

A (x)

and

B (x)

be the OGFs of sequences

(a_{n})

and

(b_{n})

, respectively. The coefficient

c_{n}

of the product

C (x) = A (x) B (x)

is given by

c_{n} = k = 0 \sum n a_{k} b_{n - k} .

This is called the convolution of

(a_{n})

and

(b_{n})

Proof.

This is immediate from the definition of the product of formal power series:

A (x) B (x) = \sum_{n} (\sum_{k = 0}^{n} a_{k} b_{n - k}) x^{n}

. □

3 Fibonacci Numbers and Binet's Formula

Definition 5 (Fibonacci sequence).

The Fibonacci sequence is defined by

F_{0} = 0

F_{1} = 1

, and

F_{n} = F_{n - 1} + F_{n - 2}

for

n \geq 2

Theorem 6 (Binet's formula).

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

where

φ = \frac{1 + 5}{2}

and

ψ = \frac{1 - 5}{2}

Proof.

Set

F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}

. Multiplying the recurrence

F_{n} = F_{n - 1} + F_{n - 2}

x^{n}

and summing over

n \geq 2

yields

F (x) - F_{1} x - F_{0} = x (F (x) - F_{0}) + x^{2} F (x) .

Solving for

F (x)

gives

F (x) (1 - x - x^{2}) = x

, whence

F (x) = \frac{x}{1 - x - x ^{2}}

We now perform a partial fraction decomposition. Since

1 - x - x^{2} = - (x - (- φ^{- 1})) (x - (- ψ^{- 1}))

, we obtain

F (x) = \frac{1}{5} (\frac{1}{1 - φ x} - \frac{1}{1 - ψ x}) .

Expanding

\frac{1}{1 - αx} = \sum_{n = 0}^{\infty} α^{n} x^{n}

and reading off the coefficient of

x^{n}

gives

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

. □

4 The Generating Function for the Catalan Numbers

Definition 7 (Catalan number).

The

n

-th Catalan number is

C_{n} = \frac{1}{n + 1} (n 2 n)

for

n \geq 0

Theorem 8.

The OGF

C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}

of the Catalan numbers is

C (x) = \frac{1 - 1 - 4 x}{2 x} .

Proof.

The Catalan numbers satisfy the recurrence

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

for

n \geq 1

, with

C_{0} = 1

. In terms of the OGF, this translates to

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

. Solving the quadratic

x C^{2} - C + 1 = 0

yields

C (x) = \frac{1 \pm 1 - 4 x}{2 x}

. The initial condition

C (0) = C_{0} = 1

forces us to take the minus sign. □

5 The Generating Function for the Partition Numbers

Definition 9 (Partition number).

The number of ways to write a nonneg\/ative integer

n

as a sum of positive integers, disregarding order, is called the partition number

p (n)

Theorem 10 (Euler's generating function for the partition numbers).

n = 0 \sum \infty p (n) x^{n} = k = 1 \prod \infty \frac{1}{1 - x ^{k}}

Proof.

For each positive integer

k

, using

k

exactly

j

times in a partition corresponds to the monomial

x^{kj}

. The generating function for the number of times

k

can be used is

\frac{1}{1 - x ^{k}} = j = 0 \sum \infty x^{kj} .

Taking the product over all

k \geq 1

, the coefficient of

x^{n}

in the resulting product counts the number of ways to partition

n

into positive integer parts, which is

p (n)

. □

Remark 11.

A recurrence for the partition numbers can be derived from Euler's pentagonal number theorem:

\prod_{k = 1}^{\infty} (1 - x^{k}) = \sum_{m = - \infty}^{\infty} (- 1)^{m} x^{m (3 m - 1) /2}

Combinatorics Discrete Mathematics Textbook Generating Functions OGF

Folio Official

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

1 followers·107 articles

Generating Functions I (Ordinary): Encoding Sequences as Power Series

1 Definition of Ordinary Generating Functions

2 Products and Convolution

3 Fibonacci Numbers and Binet's Formula

4 The Generating Function for the Catalan Numbers

5 The Generating Function for the Partition Numbers

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

Generating Functions I (Ordinary): Encoding Sequences as Power Series

1 Definition of Ordinary Generating Functions

2 Products and Convolution

3 Fibonacci Numbers and Binet's Formula

4 The Generating Function for the Catalan Numbers

5 The Generating Function for the Partition Numbers

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