A recurrence relation is useful only after we learn how to see all of its terms at once. If a sequence is presented as $a_{n+2}=a_{n+1}+a_n$, term-by-term computation tells us the next number, but it hides the global shape of the sequence. A generating function packages the whole sequence into a single formal object, so that shifting indices, adding recurrences, and extracting coefficients become algebraic operations.

The surprise is that the variable in a generating function does not have to be a small real or complex number. In many applications it is safer to treat it as a bookkeeping symbol. This is especially important over finite fields: if $(a_n)_{n\geq 0}$ is a sequence with $a_n \in \mathbb{F}_2$, then its generating function naturally lives in the formal [power series](/page/Power%20Series) ring $\mathbb{F}_2[[X]]$, where convergence is not analytic but coefficientwise.

[example: Fibonacci Numbers as One Object] Let $(F_n)_{n\geq 0}$ be defined by $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for all $n\geq 0$. Its ordinary generating function is \begin{align*} F(X)=\sum_{n=0}^{\infty}F_nX^n. \end{align*} Multiplying the recurrence by $X^{n+2}$ and summing over all $n\geq 0$ gives \begin{align*} \sum_{n=0}^{\infty}F_{n+2}X^{n+2}=\sum_{n=0}^{\infty}F_{n+1}X^{n+2}+\sum_{n=0}^{\infty}F_nX^{n+2}. \end{align*} For the left-hand side, put $m=n+2$. Then $m\geq 2$, so \begin{align*} \sum_{n=0}^{\infty}F_{n+2}X^{n+2}=\sum_{m=2}^{\infty}F_mX^m=F(X)-F_0-F_1X=F(X)-X. \end{align*} For the first sum on the right-hand side, factor out one $X$ and put $m=n+1$: \begin{align*} \sum_{n=0}^{\infty}F_{n+1}X^{n+2}=X\sum_{n=0}^{\infty}F_{n+1}X^{n+1}=X\sum_{m=1}^{\infty}F_mX^m=XF(X), \end{align*} because $F_0=0$. For the second sum on the right-hand side, \begin{align*} \sum_{n=0}^{\infty}F_nX^{n+2}=X^2\sum_{n=0}^{\infty}F_nX^n=X^2F(X). \end{align*} Substituting these three identities into the summed recurrence gives \begin{align*} F(X)-X=XF(X)+X^2F(X). \end{align*} Move the two terms involving $F(X)$ to the left: \begin{align*} F(X)-XF(X)-X^2F(X)=X. \end{align*} Factoring out $F(X)$ gives \begin{align*} (1-X-X^2)F(X)=X. \end{align*} Since $1-X-X^2$ has constant coefficient $1$, it is invertible in $\mathbb{Z}[[X]]$, and therefore \begin{align*} F(X)=\frac{X}{1-X-X^2}. \end{align*} The infinite Fibonacci sequence is therefore encoded by one rational formal power series. [/example]

That computation is not a proof that power series converge anywhere. It is an identity in a formal algebra, and that distinction is the reason generating functions are so flexible. The first task is therefore to define the ambient algebra before defining the generating function itself.

## Definition

The central definition should come first: a generating function is the act of replacing the separate entries of a sequence by coefficients of one series. This is useful only when the coefficient ring is part of the data, because the same string of coefficients behaves differently over $\mathbb{Z}$, $\mathbb{C}$, or $\mathbb{F}_2$.

[definition: Generating Function] Let $R$ be a commutative ring and let $a: \mathbb{N}\cup\{0\}\to R$ be a function, written $n\mapsto a_n$. The ordinary generating function of $(a_n)_{n\geq 0}$ is the formal power series $A(X)\in R[[X]]$ defined by \begin{align*} A(X)=\sum_{n=0}^{\infty}a_nX^n. \end{align*} [/definition]

This definition packages the page topic, but it uses two supporting objects that deserve to be isolated. First, the coefficients come from a sequence; second, the target object is a formal power series rather than an analytic function of a variable.

Before studying the series, we need a precise name for the raw data being encoded. The same list of symbols can produce different algebraic behavior depending on the coefficient ring, so the coefficient set must be included in the notion of sequence itself.

[definition: Sequence] Let $R$ be a commutative ring. A sequence over $R$ is a function $a: \mathbb{N}\cup\{0\}\to R$. Its value at $n$ is denoted $a_n$. [/definition]

The next object is a power series where the symbol $X$ is not being assigned a value. This lets us multiply infinite expressions by asking only for one coefficient at a time; each coefficient of a product uses a finite sum.

[definition: Formal Power Series] Let $R$ be a commutative ring. The formal power series ring $R[[X]]$ is the set of expressions \begin{align*} \sum_{n=0}^{\infty}c_nX^n \end{align*} with $c_n\in R$ for all $n\geq 0$, equipped with an addition operation \begin{align*} +: R[[X]]\times R[[X]]\to R[[X]] \end{align*} and a multiplication operation \begin{align*} \cdot: R[[X]]\times R[[X]]\to R[[X]], \end{align*} where addition is coefficientwise and multiplication is the Cauchy product. [/definition]

With the ambient ring now explicit, the word "ordinary" separates this construction from variants such as exponential and multivariate generating functions. It is the default convention on this page: coefficients are attached directly to powers $X^n$, with no factorials or additional variables.

[definition: Ordinary Generating Function] Let $R$ be a commutative ring and let $(a_n)_{n\geq 0}$ be a sequence over $R$. The ordinary generating function of $(a_n)_{n\geq 0}$ is the formal power series $A(X)\in R[[X]]$ defined by \begin{align*} A(X)=\sum_{n=0}^{\infty}a_nX^n. \end{align*} [/definition]

The coefficient ring becomes especially visible in characteristic $2$. Many parity questions only ask whether a count is even or odd, and reducing coefficients modulo $2$ turns cancellations into a feature rather than a nuisance.

[definition: Generating Function over $\mathbb{F}_2$] Let $(a_n)_{n\geq 0}$ be a sequence over $\mathbb{F}_2$. Its generating function is the formal power series $A(X)\in \mathbb{F}_2[[X]]$ defined by \begin{align*} A(X)=\sum_{n=0}^{\infty}a_nX^n. \end{align*} [/definition]

To talk efficiently about recovering terms, we need a notation for the coefficient of a monomial. This is the bridge from algebraic identities back to statements about individual sequence entries.

[definition: Coefficient Extraction] Let $R$ be a commutative ring. For each $n\geq 0$, the coefficient extraction operator is the map \begin{align*} [X^n]: R[[X]]\to R. \end{align*} For $A(X)=\sum_{m=0}^{\infty}a_mX^m\in R[[X]]$, the value of this map is \begin{align*} [X^n]A(X)=a_n. \end{align*} [/definition]

The coefficient notation makes the definition reversible, and that reversibility has to be stated as a theorem because all later calculations depend on it. Once equality of formal series is the same as equality of every coefficient, an algebraic identity in $R[[X]]$ becomes a controlled way to prove infinitely many scalar identities at once.

[quotetheorem:8148]