---
tag: 0HH6JX5WZZ
kind: definition
name: Generating function
msc: [05A15]
defines: 0PHAC833JF
uses: [072W67KFYK]
sources:
  - url: https://en.wikipedia.org/wiki/Generating_function
    locator: Ordinary generating function (OGF)
---

## Definition

Let $R$ be a commutative ring and let $(a_n)_{n \ge 0}$ be a sequence in $R$.
The ordinary generating function of $(a_n)$ is the [[formal power series|072W67KFYK]]
$$A(x) = \sum_{n \ge 0} a_n x^n \in R[\![x]\!].$$

## Remarks

Example: the sequence $1, 1, 1, \dots$ has the generating function $\sum_n x^n = \frac{1}{1 - x}$, the [[geometric series|0R8JR0ARJ4]].
Operations on sequences become operations on series. The [[product of power series|0H6KWAYS87]] corresponds to the convolution $c_n = \sum_{i+j=n} a_i b_j$.
The [[exponential generating function|0KE6NBTVY8]] is a variant with the weights $x^n / n!$.

## Explanations

### L1 human

A generating function stores a whole sequence as the coefficients of one power series.
Algebra with the series then gives facts about the sequence, such as recurrences or closed formulas.