Generating function

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 $$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. Operations on sequences become operations on series. The product of power series corresponds to the convolution $c_n = \sum_{i+j=n} a_i b_j$. The exponential generating function 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.