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] This theorem is the licence for the method. A generating-function identity is not a decorative shorthand; it is exactly a family of coefficient identities indexed by $n$. ## Algebra of Coefficients The elementary operations on generating functions correspond to elementary operations on sequences, but with a crucial difference: multiplication blends earlier terms by convolution. This is where many counting arguments become shorter, because choosing an object in stages becomes multiplying the series for each stage. ### Linear Operations Before multiplication enters the story, the algebra should preserve the operations that are already available for sequences. If two counting problems are alternatives, their coefficients add; if each object is weighted by a fixed scalar, each coefficient is scaled by that scalar. The first rule says that ordinary generating functions respect these termwise operations. [quotetheorem:8149] Addition is coefficientwise, so it behaves exactly as expected and needs little machinery after the theorem above. Multiplication is richer: to define a product of infinite series without convergence, we need a rule that computes each coefficient using only finitely many earlier coefficients. The decompositions $n=i+j$ provide exactly that finite rule. ### Cauchy Products and Convolution The product of two infinite series cannot be defined by expanding all terms at once, because that would mix infinitely many symbols without a coefficientwise stopping rule. The right rule asks a finite question for each degree $n$: which pairs of degrees add to $n$? [definition: Cauchy Product] Let $R$ be a commutative ring. For \begin{align*} A(X)=\sum_{n=0}^{\infty}a_nX^n\in R[[X]],\qquad B(X)=\sum_{n=0}^{\infty}b_nX^n\in R[[X]], \end{align*} the Cauchy product $A(X)B(X)$ is the formal power series \begin{align*} A(X)B(X)=\sum_{n=0}^{\infty}\left(\sum_{i=0}^{n}a_ib_{n-i}\right)X^n. \end{align*} [/definition] The definition turns multiplication into a counting device, but the useful statement is not merely the formula for the product. We need the theorem that identifies this product with the generating function of a new sequence, because that is what lets a combinatorial construction be translated into algebra and then back into coefficients. [quotetheorem:8150] Here is the smallest example where multiplication does real combinatorial work rather than merely changing notation. [example: Counting Ordered Pairs] Let $a_n=1$ for every $n\geq 0$, and work in $\mathbb{Z}[[X]]$. Its ordinary generating function is \begin{align*} A(X)=\sum_{n=0}^{\infty}X^n=1+X+X^2+\cdots. \end{align*} The formal geometric identity is verified coefficientwise: \begin{align*} (1-X)A(X)=\left(\sum_{n=0}^{\infty}X^n\right)-\left(\sum_{n=0}^{\infty}X^{n+1}\right)=1. \end{align*} Thus $A(X)=1/(1-X)$ in $\mathbb{Z}[[X]]$. By the Cauchy product definition, the coefficient of $X^n$ in $A(X)^2$ is \begin{align*} [X^n]A(X)^2=\sum_{i=0}^{n}a_ia_{n-i}. \end{align*} Since $a_i=1$ and $a_{n-i}=1$ for each $i=0,1,\ldots,n$, this becomes \begin{align*} [X^n]A(X)^2=\sum_{i=0}^{n}1\cdot 1=\sum_{i=0}^{n}1=n+1. \end{align*} The same index $i$ parametrizes the ordered pairs \begin{align*} (i,n-i)\qquad 0\leq i\leq n, \end{align*} so there are exactly $n+1$ ordered pairs $(i,j)$ of nonnegative integers with $i+j=n$. Therefore $A(X)^2$ has coefficients $1,2,3,\ldots$, recording these ordered-pair counts degree by degree. [/example] Over $\mathbb{F}_2$, the same example changes character because even counts vanish. This is not a defect; it is often the point. [example: The Geometric Series over $\mathbb{F}_2$] In $\mathbb{F}_2[[X]]$, let \begin{align*} A(X)=\sum_{n=0}^{\infty}X^n=1+X+X^2+\cdots. \end{align*} Multiplying by $X$ shifts every term up by one degree: \begin{align*} XA(X)=\sum_{n=0}^{\infty}X^{n+1}=X+X^2+X^3+\cdots. \end{align*} Therefore \begin{align*} (1+X)A(X)=A(X)+XA(X)=\left(1+X+X^2+\cdots\right)+\left(X+X^2+X^3+\cdots\right). \end{align*} The constant coefficient is $1$. For every $n\geq 1$, the coefficient of $X^n$ is $1+1$, and in $\mathbb{F}_2$ we have $1+1=0$. Hence \begin{align*} (1+X)A(X)=1. \end{align*} Thus $A(X)$ is the multiplicative inverse of $1+X$ in $\mathbb{F}_2[[X]]$, so \begin{align*} A(X)=\frac{1}{1+X}. \end{align*} The same geometric series that has denominator $1-X$ over $\mathbb{Z}$ has denominator $1+X$ over $\mathbb{F}_2$, because subtraction and addition coincide in characteristic $2$. [/example] ## Recurrences and Rationality Generating functions are most powerful when a recurrence shifts the sequence. A shift of the index becomes multiplication by $X$, except for the finitely many initial terms that spill out at the beginning. Linear recurrences therefore become algebraic equations for the generating function. ### Constant-Coefficient Recurrences A recurrence is a promise that the tail of a sequence is not independent data. After finitely many initial values, every later term is forced by a fixed linear rule. This is the kind of finite memory that generating functions can detect algebraically. [definition: Linear Recurrence with Constant Coefficients] Let $R$ be a commutative ring. A sequence $(a_n)_{n\geq 0}$ over $R$ satisfies a linear recurrence with constant coefficients of order $d\geq 1$ if there exist $r_1,\ldots,r_d\in R$ such that \begin{align*} a_{n+d}=r_1a_{n+d-1}+r_2a_{n+d-2}+\cdots+r_da_n \end{align*} for all $n\geq 0$. [/definition] The algebraic shadow of such a recurrence is a fraction of polynomials. To make that phrase meaningful in a formal power series ring, the denominator must be invertible as a formal series; this is the point of requiring a unit constant term in the definition below. ### Rational Series When the algebraic equation coming from a recurrence is solved for the generating function, the result is a quotient of polynomials. In a formal power series ring, such a quotient is meaningful precisely when the denominator has an invertible constant term, so that division can be performed coefficient by coefficient. [definition: Rational Generating Function] Let $R$ be a commutative ring. A formal power series $A(X)\in R[[X]]$ is rational if there exist polynomials $P(X),Q(X)\in R[X]$ such that $Q(0)$ is a unit in $R$ and \begin{align*} A(X)=\frac{P(X)}{Q(X)} \end{align*} in $R[[X]]$. [/definition] The condition that $Q(0)$ be a unit is what allows division by $Q(X)$ inside $R[[X]]$. This definition is designed to capture the output of the recurrence method: after multiplying a recurrence by powers of $X$ and summing, all tail terms collapse into a polynomial equation with an invertible denominator. [quotetheorem:8155] The converse is equally important because rationality should not be a one-way diagnostic. Once a denominator has positive degree, its coefficients can be read as a finite memory rule for the tail of the sequence; if no positive-degree denominator is needed, the series is a polynomial and the tail is eventually zero. The next theorem separates these two possibilities so that the recurrence statement does not hide a convention about order zero. [quotetheorem:8151] The phrase “for all sufficiently large $n$” matters. The numerator of the rational expression controls finitely many initial coefficients, while the denominator controls the eventual recurrence. [example: A Binary Periodic Sequence] Let $(a_n)_{n\geq 0}$ be the sequence over $\mathbb{F}_2$ with $a_n=1$ for even $n$ and $a_n=0$ for odd $n$. Its ordinary generating function is \begin{align*} A(X)=\sum_{k=0}^{\infty}X^{2k}=1+X^2+X^4+\cdots. \end{align*} Multiplying by $X^2$ shifts the even powers up by two degrees: \begin{align*} X^2A(X)=\sum_{k=0}^{\infty}X^{2k+2}=\sum_{k=1}^{\infty}X^{2k}=X^2+X^4+X^6+\cdots. \end{align*} Therefore \begin{align*} (1+X^2)A(X)=A(X)+X^2A(X)=(1+X^2+X^4+\cdots)+(X^2+X^4+X^6+\cdots). \end{align*} The coefficient of $X^0$ is $1$. If $n$ is odd, both summands have coefficient $0$ at $X^n$. If $n=2k$ with $k\geq 1$, the coefficient of $X^n$ is $1+1=0$ in $\mathbb{F}_2$. Hence \begin{align*} (1+X^2)A(X)=1. \end{align*} So $A(X)$ is the inverse of $1+X^2$ in $\mathbb{F}_2[[X]]$, and \begin{align*} A(X)=\frac{1}{1+X^2}. \end{align*} Since $-1=1$ in $\mathbb{F}_2$, the same denominator can also be written as $1-X^2$: \begin{align*} A(X)=\frac{1}{1-X^2}. \end{align*} Finally, writing $A(X)=\sum_{n=0}^{\infty}a_nX^n$, the coefficient of $X^{n+2}$ in $(1+X^2)A(X)$ is $a_{n+2}+a_n$. The right-hand side $1$ has coefficient $0$ in every degree $n+2\geq 2$, so $a_{n+2}+a_n=0$, equivalently $a_{n+2}=a_n$. The denominator records the period-two recurrence, with addition and subtraction identical in characteristic $2$. [/example] Not every sequence has such a finite description. Generating functions make the failure visible: a sequence may be perfectly well-defined term by term while its generating function refuses to be rational. [example: A Sparse Non-Rational Pattern] Let $(a_n)_{n\geq 0}$ be the sequence over $\mathbb{F}_2$ with $a_n=1$ exactly when $n=2^k$ for some $k\geq 0$, and $a_n=0$ otherwise. Its generating function is \begin{align*} A(X)=\sum_{k=0}^{\infty}X^{2^k}=X+X^2+X^4+X^8+\cdots\in \mathbb{F}_2[[X]]. \end{align*} We show that $A(X)$ is not rational. Suppose, toward a contradiction, that \begin{align*} A(X)=\frac{P(X)}{Q(X)} \end{align*} with $P(X),Q(X)\in\mathbb{F}_2[X]$ and $Q(0)\neq 0$. Since the only nonzero element of $\mathbb{F}_2$ is $1$, write \begin{align*} Q(X)=1+q_1X+\cdots+q_dX^d. \end{align*} If $d=0$, then $Q(X)=1$, so $A(X)=P(X)$ would be a polynomial. But $A(X)$ has a nonzero coefficient at $X^{2^k}$ for every $k\geq 0$, so it has infinitely many nonzero terms. Hence $d\geq 1$. Multiplying by $Q(X)$ gives \begin{align*} Q(X)A(X)=P(X). \end{align*} For $m\geq d$, the coefficient of $X^m$ in $Q(X)A(X)$ is \begin{align*} a_m+q_1a_{m-1}+q_2a_{m-2}+\cdots+q_da_{m-d}. \end{align*} Let $E=\deg P$. For every $m>E$, the coefficient of $X^m$ in $P(X)$ is $0$, so \begin{align*} a_m+q_1a_{m-1}+q_2a_{m-2}+\cdots+q_da_{m-d}=0. \end{align*} In $\mathbb{F}_2$, subtraction equals addition, so this determines \begin{align*} a_m=q_1a_{m-1}+q_2a_{m-2}+\cdots+q_da_{m-d} \end{align*} for every $m>E$. Thus each later block $(a_{m-d+1},\ldots,a_m)$ is determined by the previous block. There are only $2^d$ possible blocks in $\mathbb{F}_2^d$, so two blocks must repeat, and from the first repetition onward the sequence is periodic. Therefore the support set \begin{align*} \{n\geq 0:a_n=1\}=\{1,2,4,8,\ldots\} \end{align*} would be eventually periodic with some period $p\geq 1$. Choose $k$ so large that $2^k$ is past the preperiod and $2^k>p$. Since $a_{2^k}=1$, eventual periodicity gives \begin{align*} a_{2^k+p}=a_{2^k}=1. \end{align*} Therefore $2^k+p$ must be a power of two. But $p>0$ gives \begin{align*} 2^k<2^k+p, \end{align*} and $p<2^k$ gives \begin{align*} 2^k+p<2^k+2^k=2^{k+1}. \end{align*} So $2^k+p$ lies strictly between two consecutive powers of two, which is impossible. Hence $A(X)$ is not rational over $\mathbb{F}_2$. [/example] ## Formal Versus Analytic Meaning The same expression can be read in two different languages. In formal algebra, $1/(1-X)$ means the unique formal power series whose product with $1-X$ is $1$. In analysis, it may mean a function defined only for $|X|<1$. Confusing these readings leads to false objections and false proofs. ### Domains of Convergence Sometimes the variable is no longer a bookkeeping symbol. If the coefficients are complex numbers, we may ask for which complex inputs the series has an analytic value. This produces a genuine function, but only on the set where the infinite sum converges. [definition: Analytic Generating Function] Let $(a_n)_{n\geq 0}$ be a sequence over $\mathbb{C}$, and define \begin{align*} D=\left\{z\in\mathbb{C}:\sum_{n=0}^{\infty}a_nz^n\text{ converges in }\mathbb{C}\right\}. \end{align*} The analytic generating function associated to $(a_n)_{n\geq 0}$ is the function $A:D\to\mathbb{C}$ defined by \begin{align*} A(z)=\sum_{n=0}^{\infty}a_nz^n. \end{align*} [/definition] The analytic viewpoint adds questions about [radius of convergence](/theorems/262), singularities, and asymptotic growth. The formal viewpoint keeps only the coefficient algebra. To see the difference without any analytic hypotheses, the geometric series identity should be stated inside $R[[X]]$ before it is compared with its complex analytic counterpart. ### Formal Identities The geometric series is the test case for separating formal algebra from analysis. Formally, there is no need to discuss $|X|<1$; the identity is verified by multiplying series and comparing coefficients. [quotetheorem:8152] This identity is valid over every commutative ring, with no convergence hypothesis. Over $\mathbb{C}$, it agrees with the analytic identity only inside the unit disc. [example: A Formal Identity Without Global Analytic Equality] Let \begin{align*} A(X)=\sum_{n=0}^{\infty}X^n\in\mathbb{C}[[X]]. \end{align*} In the formal power series ring, multiplication by $X$ shifts every coefficient up by one degree: \begin{align*} XA(X)=\sum_{n=0}^{\infty}X^{n+1}=X+X^2+X^3+\cdots. \end{align*} Therefore \begin{align*} (1-X)A(X)=A(X)-XA(X). \end{align*} The coefficient of $X^0$ in $A(X)-XA(X)$ is $1-0=1$. For every $n\geq 1$, the coefficient of $X^n$ is $1-1=0$. Hence \begin{align*} (1-X)A(X)=1. \end{align*} Since this is exactly the statement that $A(X)$ is the multiplicative inverse of $1-X$ in $\mathbb{C}[[X]]$, we get \begin{align*} \sum_{n=0}^{\infty}X^n=\frac{1}{1-X} \end{align*} as a formal identity. Now replace the bookkeeping symbol $X$ by a complex number $z$ and consider the partial sums \begin{align*} S_N=1+z+z^2+\cdots+z^N. \end{align*} If $z\neq 1$, then multiplying by $1-z$ gives \begin{align*} (1-z)S_N=1-z^{N+1}. \end{align*} Thus \begin{align*} S_N=\frac{1-z^{N+1}}{1-z}. \end{align*} When $|z|<1$, we have $z^{N+1}\to 0$, so \begin{align*} S_N\to \frac{1}{1-z}. \end{align*} When $|z|\geq 1$, the terms $z^n$ do not tend to $0$: if $|z|>1$ their absolute values grow, and if $|z|=1$ their absolute values stay equal to $1$. Therefore the analytic series $\sum_{n=0}^{\infty}z^n$ cannot converge for $|z|\geq 1$. The formal identity holds everywhere inside coefficient algebra, while the analytic equality describes a function only on the open unit disk. [/example] There is a second common variation, used when labels rather than sizes are being counted. Ordinary generating functions attach $a_n$ directly to $X^n$; labelled constructions often require the normalization by $n!$ so that relabelling symmetries are accounted for algebraically. That normalization forces us to work in a setting where the factorials are invertible. ### Exponential Series Ordinary generating functions attach coefficients directly to powers of $X$. Labelled structures often behave better after dividing the degree-$n$ coefficient by $n!$, because the factorial records the number of relabellings. This normalization only makes sense in rings where those factorials can be divided by. [definition: Exponential Generating Function] Let $K$ be a field of characteristic $0$, and let $(a_n)_{n\geq 0}$ be a sequence over $K$. The exponential generating function of $(a_n)_{n\geq 0}$ is \begin{align*} E(X)=\sum_{n=0}^{\infty}a_n\frac{X^n}{n!}\in K[[X]]. \end{align*} [/definition] This page mostly uses ordinary generating functions because they are the correct tool for sequences over $\mathbb{F}_2$. Factorials may vanish in finite characteristic, so exponential generating functions require extra care there. ## Combinatorial Constructions Generating functions work well when a construction has a size parameter and the size of a composite object is the sum of the sizes of its parts. The algebra is then not a metaphor: addition represents alternatives, multiplication represents ordered combination, and coefficient extraction returns the number of objects of a given size. ### Graded Classes To turn a family of finite sets into a sequence, the objects must be sorted by size. The counting sequence is the bookkeeping map that sends a size to the number of objects of that size. [definition: Counting Sequence] Let $\mathcal{A}=\bigcup_{n=0}^{\infty}\mathcal{A}_n$ be a disjoint union of finite sets. The counting sequence of $\mathcal{A}$ is the function \begin{align*} a:\mathbb{N}\cup\{0\}\to \mathbb{Z}_{\geq 0}. \end{align*} It is defined by sending $n$ to $|\mathcal{A}_n|$. Its $n$th term is denoted \begin{align*} a_n=|\mathcal{A}_n|. \end{align*} [/definition] Once a class is graded by size, the next question is how to store the whole counting sequence without losing the grading. Its generating function records all counting numbers at once. Since these are cardinalities, the natural coefficient ring is $\mathbb{Z}$: it keeps exact counts before any later reduction modulo a prime or extension to a larger ring. [definition: Generating Function of a Graded Class] Let $\mathcal{A}=\bigcup_{n=0}^{\infty}\mathcal{A}_n$ be a disjoint union of finite sets with counting sequence $(a_n)_{n\geq 0}$. The ordinary generating function of $\mathcal{A}$ is \begin{align*} A(X)=\sum_{n=0}^{\infty}|\mathcal{A}_n|X^n\in \mathbb{Z}[[X]]. \end{align*} [/definition] The next theorem is the cleanest expression of why products appear everywhere in enumerative combinatorics. If an object of total size $n$ is built by choosing a size $i$ object from one class and a size $n-i$ object from another, then the same finite sum appears both in the counting problem and in the Cauchy product. ### Product Constructions The main reason for grading a class is that many constructions build a new object from smaller pieces. When size is additive across the pieces, the number of choices of total size $n$ is the same convolution that appears in the product of generating functions. [quotetheorem:8153] For unordered or quotient constructions, ordinary multiplication is usually not enough. The generating function still helps, but the algebra must be chosen to match the symmetry. [remark: What Generating Functions Do Not Automatically Know] An ordinary generating function remembers only the coefficient sequence. It does not remember the objects that were counted, any canonical bijection between two classes, or internal symmetries unless those data are encoded by additional variables or a richer generating function. [/remark] This limitation is healthy. A small rational expression may prove that two counting sequences agree, but it does not by itself construct a bijection between the counted sets. ## Algebraic Generating Functions Rational generating functions are controlled by linear recurrences. Some naturally occurring series are not rational but still satisfy polynomial equations. These sit in the next layer of structure and appear often in recursive combinatorial classes. Rationality is too restrictive for many recursive counting problems, because nonlinear decompositions lead to polynomial equations rather than linear denominator relations. The next definition keeps the same formal power series setting while allowing the series to satisfy an equation involving both $X$ and the unknown series itself. [definition: Algebraic Generating Function] Let $K$ be a field. A formal power series $A(X)\in K[[X]]$ is algebraic over $K(X)$ if there exists a nonzero polynomial $P(X,Y)\in K[X,Y]$ such that \begin{align*} P(X,A(X))=0 \end{align*} in $K[[X]]$. [/definition] The first question after making the definition is whether it really extends the rational theory or starts a separate subject. A fraction $P(X)/Q(X)$ satisfies a linear polynomial equation after clearing the denominator, so rational series must sit inside the algebraic class. Stating this inclusion matters because it places the recurrence-controlled theory inside the broader theory used for recursive decompositions such as the Catalan equation. [quotetheorem:8154] A standard example is supplied by the Catalan numbers, where the recurrence splits an object into two independent subobjects. [example: Catalan Numbers] Let $(C_n)_{n\geq 0}$ be defined by $C_0=1$ and \begin{align*} C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i} \end{align*} for every $n\geq 0$. Put \begin{align*} C(X)=\sum_{n=0}^{\infty}C_nX^n. \end{align*} We compute the coefficient sequence of $XC(X)^2$. By the Cauchy product rule for formal power series, the coefficient of $X^n$ in $C(X)^2$ is \begin{align*} [X^n]C(X)^2=\sum_{i=0}^{n}C_iC_{n-i}. \end{align*} Using the recurrence, this becomes \begin{align*} [X^n]C(X)^2=C_{n+1}. \end{align*} Multiplication by $X$ shifts coefficients up one degree, so \begin{align*} XC(X)^2=\sum_{n=0}^{\infty}C_{n+1}X^{n+1}. \end{align*} Reindex with $m=n+1$. Then $m\geq 1$, and \begin{align*} XC(X)^2=\sum_{m=1}^{\infty}C_mX^m. \end{align*} Since $C_0=1$, the full generating function is \begin{align*} C(X)=C_0+\sum_{m=1}^{\infty}C_mX^m. \end{align*} Therefore \begin{align*} C(X)=1+XC(X)^2. \end{align*} Equivalently, \begin{align*} XC(X)^2-C(X)+1=0. \end{align*} Thus $C(X)$ satisfies the nonzero polynomial equation $XY^2-Y+1=0$ with $Y=C(X)$, so $C(X)$ is algebraic over the rational function field in $X$. The quadratic equation records exactly the recursive split of a Catalan object into a left part counted by $C_i$ and a right part counted by $C_{n-i}$. [/example] This example also marks the boundary of the rational theory. The Catalan generating function is algebraic, but its coefficients do not satisfy a constant-coefficient linear recurrence. ## Beyond and Connected Topics Generating functions sit between algebra, combinatorics, and analysis. The formal power series viewpoint connects directly to [rings](/page/Ring), [polynomial rings](/page/Polynomial%20Ring), and [field extensions](/page/Field%20Extension), because rationality and algebraicity are statements inside algebraic structures. In enumerative combinatorics, ordinary generating functions are the first step toward symbolic methods, multivariate generating functions, and partition identities. Adding variables records more statistics; replacing ordinary products with cycle index series records symmetry. In recurrence theory and automata, generating functions over finite fields such as $\mathbb{F}_2[[X]]$ expose eventual periodicity, linear feedback shift registers, and binary sequence structure. This is the natural context for parity sequences and many graph-theoretic encodings. In complex analysis, analytic generating functions connect coefficient growth with singularities. A formal identity may become an analytic tool once a [radius of convergence](/theorems/265) is known, and singularity analysis turns local behaviour near a pole or branch point into asymptotics for coefficients. ## References Androma, [Ring](/page/Ring). Androma, [Polynomial Ring](/page/Polynomial%20Ring). Androma, [Field Extension](/page/Field%20Extension). Androma, [Cambridge IB Markov Chains](/page/Cambridge%20IB%20Markov%20Chains). Androma, [Cambridge II Algebraic Geometry](/page/Cambridge%20II%20Algebraic%20Geometry). Androma, [Cambridge II Analysis of Functions](/page/Cambridge%20II%20Analysis%20of%20Functions). Androma, [Cambridge II Coding and Cryptography](/page/Cambridge%20II%20Coding%20and%20Cryptography). Herbert Wilf, *generatingfunctionology* (2006). Philippe Flajolet and Robert Sedgewick, *Analytic Combinatorics* (2009). Richard Stanley, *Enumerative Combinatorics, Volume 1* (2012). Miklós Bóna, *A Walk Through Combinatorics* (2016).