Recurrences and generating functions: what happens when you turn a sequence into a function

A generating function is the "business card" of a sequence. Multiplication becomes convolution, and recurrences become algebraic equations. We derive the closed form for the Fibonacci numbers (Binet's formula) as a showcase of the method.

Folio Official

March 1, 2026

You have set up a recurrence, but you cannot find a closed-form solution – a frustrating and common experience. The generating function is a device that packages a sequence into a single formal power series and, in doing so, transforms the recurrence into an algebraic equation that can be solved by routine methods.

1 Generating functions: a sequence's business card

Definition 1 (Ordinary generating function).

The ordinary generating function (OGF) of a sequence

{a_{n}}_{n = 0}^{\infty}

is the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots

Remark 2.

The word "formal" is critical. We do not care whether the series converges;

x

is not a variable into which we substitute concrete values. Rather,

x

serves as a bookkeeping device – a shelf on which to arrange the coefficients

a_{n}

. This deliberate indifference to convergence is what makes generating functions so flexible.

2 Basic generating functions

Example 3 (Geometric series).

The generating function of the constant sequence

a_{n} = 1

(for

n \geq 0

) is

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

the familiar geometric series formula.

Example 4 (

(1 + x)^{n}

and binomial coefficients).

The generating function of

a_{k} = (k n)

(for

k = 0, 1, \dots, n

, and

0

thereafter) is

k = 0 \sum n (k n) x^{k} = (1 + x)^{n},

which is the binomial theorem with

y = 1

3 Multiplication is convolution

The most powerful property of generating functions is that their product corresponds to convolution of the coefficient sequences.

Theorem 5 (Product and convolution).

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

and

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

, then the product

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

has coefficients

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

which is the convolution of

{a_{n}}

and

{b_{n}}

Remark 6.

Convolution arises naturally in "two-stage selection" problems. Suppose

a_{k}

counts the number of ways to assemble

k

yen in coins, and

b_{j}

counts the number of ways to assemble

j

yen in banknotes. Then

c_{n} = \sum_{k} a_{k} b_{n - k}

counts the number of ways to assemble a total of

n

yen using a combination of coins and banknotes. In the language of generating functions, this becomes the single multiplication

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

4 The generating function of the Fibonacci sequence

Definition 7 (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

We derive the generating function $F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}$ from the recurrence.

Theorem 8.

The generating function of the Fibonacci sequence is

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

Proof.

Multiply both sides of the recurrence

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

x^{n}

and sum over

n \geq 2

n = 2 \sum \infty F_{n} x^{n} = n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n} .

The left-hand side is

F (x) - F_{0} - F_{1} x = F (x) - x

. On the right, the first sum is

x (F (x) - F_{0}) = x F (x)

and the second is

x^{2} F (x)

Thus

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

, which gives

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

. □

5 Binet's formula: from generating function to closed form

We perform a partial fraction decomposition of $F (x) = x / (1 - x - x^{2})$ . Factoring $1 - x - x^{2} = - (x - α) (x - β)$ , where $α$ and $β$ are the roots of $x^{2} + x - 1 = 0$ :

α = \frac{- 1 + 5}{2}, β = \frac{- 1 - 5}{2} .

A partial fraction decomposition followed by geometric series expansion yields the celebrated result.

Theorem 9 (Binet's formula).

F_{n} = \frac{1}{5} [(\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}] .

Remark 10.

That the integer sequence

F_{n}

has a closed form involving

5

is startling at first. The resolution is that

(1 - 5) /2

has absolute value less than

1

, so its

n

-th power vanishes as

n \to \infty

. Asymptotically,

F_{n}

is governed by the golden ratio

φ = (1 + 5) /2

; more precisely,

F_{n} = ⌊ φ^{n} / 5 + 1/2 ⌋

6 The generating function method: a recipe

The general procedure for solving a recurrence via generating functions consists of four steps:

Multiply both sides of the recurrence by $x^{n}$ and sum over the appropriate range.
Express everything in terms of the generating function $A (x)$ to obtain an algebraic equation.
Solve for $A (x)$ in closed form.
Extract the coefficient $a_{n}$ via partial fractions, known expansions, or other techniques.

Remark 11.

The essence of this method is a translation: a recurrence (a statement in the discrete world) becomes an algebraic equation (a statement in the continuous world). We solve the equation in the continuous world and then translate the answer back. Generating functions serve as a bridge between the discrete and the continuous.

7 Takeaway

A generating function packages a sequence into a formal power series – a compact "business card" for the sequence.
The product of generating functions corresponds to convolution, automating multi-stage counting.
The Fibonacci generating function is $x / (1 - x - x^{2})$ , from which Binet's formula follows.
The core strategy is to convert a recurrence into an algebraic equation and solve it there.

In the next article, we meet the Catalan numbers – a single sequence that, mysteriously, answers at least five apparently unrelated counting problems.

Combinatorics Mathematics Between the Lines

Folio Official

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

1 followers·107 articles

Recurrences and generating functions: what happens when you turn a sequence into a function

Folio Official

March 1, 2026

1 Generating functions: a sequence's business card

Definition 1 (Ordinary generating function).

The ordinary generating function (OGF) of a sequence

{a_{n}}_{n = 0}^{\infty}

is the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots

Remark 2.

The word "formal" is critical. We do not care whether the series converges;

x

is not a variable into which we substitute concrete values. Rather,

x

serves as a bookkeeping device – a shelf on which to arrange the coefficients

a_{n}

. This deliberate indifference to convergence is what makes generating functions so flexible.

2 Basic generating functions

Example 3 (Geometric series).

The generating function of the constant sequence

a_{n} = 1

(for

n \geq 0

) is

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

the familiar geometric series formula.

Example 4 (

(1 + x)^{n}

and binomial coefficients).

The generating function of

a_{k} = (k n)

(for

k = 0, 1, \dots, n

, and

0

thereafter) is

k = 0 \sum n (k n) x^{k} = (1 + x)^{n},

which is the binomial theorem with

y = 1

3 Multiplication is convolution

The most powerful property of generating functions is that their product corresponds to convolution of the coefficient sequences.

Theorem 5 (Product and convolution).

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

and

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

, then the product

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

has coefficients

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

which is the convolution of

{a_{n}}

and

{b_{n}}

Remark 6.

Convolution arises naturally in "two-stage selection" problems. Suppose

a_{k}

counts the number of ways to assemble

k

yen in coins, and

b_{j}

counts the number of ways to assemble

j

yen in banknotes. Then

c_{n} = \sum_{k} a_{k} b_{n - k}

counts the number of ways to assemble a total of

n

yen using a combination of coins and banknotes. In the language of generating functions, this becomes the single multiplication

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

4 The generating function of the Fibonacci sequence

Definition 7 (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

We derive the generating function $F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}$ from the recurrence.

Theorem 8.

The generating function of the Fibonacci sequence is

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

Proof.

Multiply both sides of the recurrence

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

x^{n}

and sum over

n \geq 2

n = 2 \sum \infty F_{n} x^{n} = n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n} .

The left-hand side is

F (x) - F_{0} - F_{1} x = F (x) - x

. On the right, the first sum is

x (F (x) - F_{0}) = x F (x)

and the second is

x^{2} F (x)

Thus

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

, which gives

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

. □

5 Binet's formula: from generating function to closed form

We perform a partial fraction decomposition of $F (x) = x / (1 - x - x^{2})$ . Factoring $1 - x - x^{2} = - (x - α) (x - β)$ , where $α$ and $β$ are the roots of $x^{2} + x - 1 = 0$ :

α = \frac{- 1 + 5}{2}, β = \frac{- 1 - 5}{2} .

A partial fraction decomposition followed by geometric series expansion yields the celebrated result.

Theorem 9 (Binet's formula).

F_{n} = \frac{1}{5} [(\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}] .

Remark 10.

That the integer sequence

F_{n}

has a closed form involving

5

is startling at first. The resolution is that

(1 - 5) /2

has absolute value less than

1

, so its

n

-th power vanishes as

n \to \infty

. Asymptotically,

F_{n}

is governed by the golden ratio

φ = (1 + 5) /2

; more precisely,

F_{n} = ⌊ φ^{n} / 5 + 1/2 ⌋

6 The generating function method: a recipe

The general procedure for solving a recurrence via generating functions consists of four steps:

Multiply both sides of the recurrence by $x^{n}$ and sum over the appropriate range.
Express everything in terms of the generating function $A (x)$ to obtain an algebraic equation.
Solve for $A (x)$ in closed form.
Extract the coefficient $a_{n}$ via partial fractions, known expansions, or other techniques.

Remark 11.

7 Takeaway

A generating function packages a sequence into a formal power series – a compact "business card" for the sequence.
The product of generating functions corresponds to convolution, automating multi-stage counting.
The Fibonacci generating function is $x / (1 - x - x^{2})$ , from which Binet's formula follows.
The core strategy is to convert a recurrence into an algebraic equation and solve it there.

In the next article, we meet the Catalan numbers – a single sequence that, mysteriously, answers at least five apparently unrelated counting problems.

Combinatorics Mathematics Between the Lines

Folio Official

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

1 followers·107 articles

Recurrences and generating functions: what happens when you turn a sequence into a function

1 Generating functions: a sequence's business card

2 Basic generating functions

3 Multiplication is convolution

4 The generating function of the Fibonacci sequence

5 Binet's formula: from generating function to closed form

6 The generating function method: a recipe

7 Takeaway

Share your expertise with the world

More from Folio Official

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

What does it mean to count? Addition, multiplication, and surjections

Recurrences and generating functions: what happens when you turn a sequence into a function

1 Generating functions: a sequence's business card

2 Basic generating functions

3 Multiplication is convolution

4 The generating function of the Fibonacci sequence

5 Binet's formula: from generating function to closed form

6 The generating function method: a recipe

7 Takeaway

Share your expertise with the world

More from Folio Official

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

What does it mean to count? Addition, multiplication, and surjections