Ordinary generating functions

For a sequence $a_0,a_1,\ldots$, its ordinary generating function is the formal expression $A(x)=\sum_{n\ge0}a_nx^n$. The notation $[x^n]A(x)$ extracts one coefficient. Equality of formal series means equality of every coefficient, not equality of sums on an interval. Addition is coefficientwise, and multiplication uses a finite Cauchy sum at each degree. Consequently these operations make sense even when no nonzero numerical input gives a convergent series.

The geometric-series identity is formal because multiplying by one minus the symbol cancels every positive-degree coefficient, leaving one. More generally a series over a field has a multiplicative inverse exactly when its constant coefficient is nonzero. Composition needs more care: substituting a series with zero constant coefficient into another formal series ensures that each resulting coefficient receives only finitely many contributions. Without that condition, an infinite sum may appear even at degree zero and no longer be defined in the purely formal setting.

Suppose an object is an ordered pair of components with additive sizes. Choosing a term from each generating function records the two sizes in the exponent of their product, and multiplying their coefficients counts the possible component choices. Summing terms of a fixed total degree gives the convolution already obtained by a direct structural decomposition. If the pair is unordered, this product generally counts each object multiple times and cannot be used without an additional symmetry argument.

A sequence of nonempty building blocks with generating function $B(x)$ has generating function $1+B+B^2+\cdots=1/(1-B)$. Nonempty means $B(0)=0$, which is precisely the condition that makes the infinite formal sum coefficientwise finite. A class with a repeatable zero-size block violates this condition: arbitrarily many such blocks would contribute to the same size. The algebraic restriction therefore has a concrete counting meaning, rather than being an arbitrary technical qualification.

To convert a recurrence, multiply by the appropriate power and sum only over the indices where it is valid. Shift the sums carefully, retaining missing initial terms. These boundary contributions often form the numerator of the rational generating function. Dropping them produces a function with the right denominator but the wrong sequence. After solving algebraically, extract the first few coefficients to check the original initial conditions before seeking a general coefficient formula.

Analytic information can later be added to a formal identity. For example the geometric series converges numerically only inside the unit disk, even though its formal identity has no such restriction. Outside that disk the rational expression may still have a numerical value, but that value is not the sum of the divergent series. Likewise singularity-based asymptotic estimates require analytic hypotheses and cannot be inferred merely by treating the bookkeeping symbol as a convenient real number. Keep those two levels of argument distinct.