Generating function

In mathematics, a generating function is a special way to represent an infinite sequence of numbers. It does this by using the numbers as the coefficients in a kind of math expression called a formal power series. Instead of writing out the whole series, we can often find a simpler closed form that still holds all the same information.

There are many types of generating functions, like ordinary generating functions and exponential generating functions. Other kinds include Lambert series, Bell series, and Dirichlet series. Almost any sequence can have a generating function, but some types work better for certain problems than others.

Generating functions are also called generating series because the series can be thought of as creating the sequence of numbers from its terms. These tools help mathematicians solve problems and find patterns in sequences more easily.

For generating functions in classical mechanics, see Generating function (physics). For generators in computer programming, see Generator (computer programming). For the moment generating function in statistics, see Moment generating function.

History

Generating functions were first used by Abraham de Moivre in 1730 to solve problems with patterns in numbers.

Later, Laplace gave them their name "generating function." Even before that, Euler used these ideas to solve problems in combinatory analysis and the theory of numbers.

Definition

A generating function is like a special bag for numbers. Instead of listing numbers one by one, we put them inside this bag, which helps us work with them more easily. This idea comes from two famous mathematicians: George Pólya, who said it’s like carrying many little objects in one bag, and Herbert Wilf, who compared it to hanging numbers on a clothesline for display.

Generating functions use special math expressions to represent sequences of numbers. These expressions don’t always need to work like regular math functions — they are more about organizing numbers in a neat way. Even though they look like normal functions, they are used in a different way to help solve problems.

Types

Generating functions help us understand sequences of numbers by turning them into expressions with powers. There are several types of generating functions.

Ordinary generating function (OGF)

When people talk about generating functions without specifying, they usually mean ordinary generating functions. For a sequence of numbers a_n, the ordinary generating function is written as a special kind of expression that adds up each number in the sequence multiplied by a power of x.

Exponential generating function (EGF)

Another type is the exponential generating function. For a sequence a_n, this function uses a special form that includes a factorial symbol (!_). These functions are often easier to work with for certain problems, especially those that deal with objects that can be labeled or arranged in different ways.

Poisson generating function

The Poisson generating function changes the exponential generating function by multiplying it by e^−x.

Lambert series

The Lambert series starts its sum at n = 1 instead of 0. This helps avoid problems with the first term.

Bell series

The Bell series involves both a number x and a prime number p. It creates a special kind of expression for sequences.

Dirichlet series generating functions (DGFs)

Dirichlet series generating functions are used for special kinds of sequences and can be linked to other mathematical ideas.

Polynomial sequence generating functions

Generating functions can also be used for sequences of polynomials, which are expressions that look like equations with variables and powers.

Other generating functions

There are many other kinds of generating functions for different types of sequences, including special polynomials and more complex expressions.

Ordinary generating functions

Examples for simple sequences

Polynomials are a special case of ordinary generating functions, corresponding to finite sequences. These are important because many finite sequences can be interpreted as generating functions, such as the Poincaré polynomial and others.

A fundamental generating function is that of the constant sequence 1, 1, 1, 1, ..., whose ordinary generating function is the geometric series ∑ₙ=₀^∞ xⁿ = 1/(1−x). The left-hand side is the Maclaurin series expansion of the right-hand side. Alternatively, the equality can be justified by multiplying the power series on the left by 1−x, and checking that the result is the constant power series 1.

Expressions for the ordinary generating function of other sequences are easily derived from this one. For instance, the substitution x → ax gives the generating function for the geometric sequence 1, a, a², a³, ... for any constant a: ∑ₙ=₀^∞ (ax)ⁿ = 1/(1−ax).

One can also introduce regular gaps in the sequence by replacing x by some power of x, so for instance for the sequence 1, 0, 1, 0, 1, 0, 1, 0, ... one gets the generating function ∑ₙ=₀^∞ x²ⁿ = 1/(1−x²).

By squaring the initial generating function, or by finding the derivative of both sides with respect to x and making a change of running variable n → n + 1, one sees that the coefficients form the sequence 1, 2, 3, 4, 5, ..., so one has ∑ₙ=₀^∞ (n + 1) xⁿ = 1/(1−x)², and the third power has as coefficients the triangular numbers 1, 3, 6, 10, 15, 21, ... whose term n is the binomial coefficient (n+2 choose 2), so that ∑ₙ=₀^∞ (n+2 choose 2) xⁿ = 1/(1−x)³.

More generally, for any non-negative integer k and non-zero real value a, it is true that ∑ₙ=₀^∞ aⁿ (n+k choose k) xⁿ = 1/(1−ax)ᵏ⁺¹.

Since 2 (n+2 choose 2) − 3 (n+1 choose 1) + (n choose 0) = n², one can find the ordinary generating function for the sequence 0, 1, 4, 9, 16, ... of square numbers by linear combination of binomial-coefficient generating sequences: G(n²; x) = ∑ₙ=₀^∞ n² xⁿ = 2/(1−x)³ − 3/(1−x)² + 1/(1−x) = x(x+1)/(1−x)³.

We may also expand alternately to generate this same sequence of squares as a sum of derivatives of the geometric series in the following form: G(n²; x) = ∑ₙ=₀^∞ n² xⁿ = ∑ₙ=₀^∞ n(n−1) xⁿ + ∑ₙ=₀^∞ n xⁿ = x² D²[1/(1−x)] + x D[1/(1−x)] = 2x²/(1−x)³ + x/(1−x)² = x(x+1)/(1−x)³.

Rational functions

The ordinary generating function of a sequence can be expressed as a rational function (the ratio of two finite-degree polynomials) if and only if the sequence is a linear recursive sequence with constant coefficients. This generalizes the examples above. Conversely, every sequence generated by a fraction of polynomials satisfies a linear recurrence with constant coefficients.

We also notice that the class of rational generating functions precisely corresponds to the generating functions that enumerate quasi-polynomial sequences of the form fₙ = p₁(n)ρ₁ⁿ + ⋯ + p_ℓ(n)ρ_ℓⁿ, where the reciprocal roots, ρᵢ ∈ ℂ, are fixed scalars and where pᵢ(n) is a polynomial in n for all 1 ≤ i ≤ ℓ.

In general, Hadamard products of rational functions produce rational generating functions. Similarly, if F(s, t) := ∑ₘ,ₙ≥₀ f(m, n) wᵐ zⁿ is a bivariate rational generating function, then its corresponding diagonal generating function, diag(F) := ∑ₙ=₀^∞ f(n, n) zⁿ, is algebraic.

Operations on generating functions

Multiplication yields convolution

Multiplication of ordinary generating functions yields a discrete convolution (the Cauchy product) of the sequences.

Shifting sequence indices

For integers m ≥ 1, we have the following two analogous identities for the modified generating functions enumerating the shifted sequence variants of ⟨gₙ−m⟩ and ⟨gₙ+m⟩, respectively:

Differentiation and integration of generating functions

We have the following respective power series expansions for the first derivative of a generating function and its integral:

The differentiation–multiplication operation of the second identity can be repeated k times to multiply the sequence by nᵏ, but that requires alternating between differentiation and multiplication. If instead doing k differentiations in sequence, the effect is to multiply by the kth falling factorial.

Using the Stirling numbers of the second kind, that can be turned into another formula for multiplying by nᵏ as follows.

A negative-order reversal of this sequence powers formula corresponding to the operation of repeated integration is defined by the zeta series transformation and its generalizations defined as a derivative-based transformation of generating functions, or alternately termwise by and performing an integral transformation on the sequence generating function.

Enumerating arithmetic progressions of sequences

In this section we give formulas for generating functions enumerating the sequence {fₐₙ₊b} given an ordinary generating function F(z), where a ≥ 2, 0 ≤ b s, and where for all integers p, q ≥ 0, we have an addition formula relation given by: jₚ₊q = k₀,p ⋅ k₀,q + ∑ᵢ=₁^min(p,q) ab₂⋯abᵢ₊₁ × kᵢ,p ⋅ kᵢ,q.

Properties of the hth convergent functions

For h ≥ 0 (though in practice when h ≥ 2), we can define the rational hth convergents to the infinite J-fraction, J^∞, expanded by: Convₕ(z) := Pₕ(z)/Qₕ(z) = j₀ + j₁z + ⋯ + j₂ʰ−₁z²ʰ−¹ + ∑ₙ=₂ʰ^∞ j̃ₕ,ₙzⁿ component-wise through the sequences, Pₕ(z) and Qₕ(z), defined recursively by:

Moreover, the rationality of the convergent function Convₕ(z) for all h ≥ 2 implies additional finite difference equations and congruence properties satisfied by the sequence of jₙ, and for Mₕ ≔ ab₂⋯abₕ₊₁ if h ‖ Mₕ then we have the congruence jₙ ≡ [zⁿ] Convₕ(z) (mod h), for non-symbolic, determinate choices of the parameter sequences {abᵢ} and {cᵢ} when h ≥ 2, that is, when these sequences do not implicitly depend on an auxiliary parameter such as q, x, or R as in the examples contained in the table below.

Examples

The next table provides examples of closed-form formulas for the component sequences found computationally (and subsequently proved correct in the cited references) in several special cases of the prescribed sequences, jₙ, generated by the general expansions of the J-fractions defined in the first subsection. Here we define 0 jₙc₁cᵢ (i ≥ 2)abᵢ (i ≥ 2)qⁿ²qq²ʰ−³(q²ʰ + q²ʰ−² − 1)q⁶ʰ−¹⁰(q²ʰ−² − 1)(a; q)ₙ1 − aqʰ−¹ − a qʰ−²(qʰ + qʰ−¹ − 1)a q²ʰ−⁴(a qʰ−² − 1)(qʰ−¹ − 1)(z q^−ⁿ; q)ₙ(q − z)/q(qʰ − z − q z + qʰ z)/q²ʰ−¹((qʰ−¹ − 1)(qʰ−¹ − z) ⋅ z)/q⁴ʰ−⁵(a; q)ₙ/(b; q)ₙ(1 − a)/(1 − b)qⁱ−²(q + a b q²ⁱ−³ + a(1 − qⁱ−¹ − qⁱ) + b(qⁱ − q − 1))/(1 − b q²ⁱ−⁴)(1 − b q²ⁱ−²)q²ⁱ−⁴(1 − b qⁱ−³)(1 − a qⁱ−²)(a − b qⁱ−²)(1 − qⁱ−¹)/((1 − b q²ⁱ−⁵)(1 − b q²ⁱ−⁴)²(1 − b q²ⁱ−³))αⁿ ⋅ (R/α)ₙRR + 2α(i − 1)(i − 1)α(R + (i − 2)α)(−1)ⁿ (x choose n)−x−((x + 2(i − 1)²)/(2i − 1)(2i − 3)){−((x − i + 2)(x + i − 1))/(4 ⋅ (2i − 3)²) for i ≥ 3; −(1/2)x(x + 1) for i = 2.}(−1)ⁿ (x + n choose n)−(x + 1)((x − 2i(i − 2) − 1)/(2i − 1)(2i − 3)){−((x − i + 2)(x + i − 1))/(4 ⋅ (2i − 3)²) for i ≥ 3; −(1/2)x(x + 1) for i = 2.}

The radii of convergence of these series corresponding to the definition of the Jacobi-type J-fractions given above are in general different from that of the corresponding power series expansions defining the ordinary generating functions of these sequences.

Examples

Square numbers

Generating functions can help us understand sequences like square numbers, where each term is n². These functions are linked to important mathematical ideas, such as the Riemann zeta function.

Generating function type	Equation
Ordinary generating function	G ( n 2 ; x ) = ∑ n = 0 ∞ n 2 x n = x ( x + 1 ) ( 1 − x ) 3 {\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}}
Exponential generating function	EG ⁡ ( n 2 ; x ) = ∑ n = 0 ∞ n 2 x n n ! = x ( x + 1 ) e x {\displaystyle \operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}}
Bell series	BG p ⁡ ( n 2 ; x ) = ∑ n = 0 ∞ ( p n ) 2 x n = 1 1 − p 2 x {\displaystyle \operatorname {BG} _{p}\left(n^{2};x\right)=\sum _{n=0}^{\infty }\left(p^{n}\right)^{2}x^{n}={\frac {1}{1-p^{2}x}}}
Dirichlet series	DG ⁡ ( n 2 ; s ) = ∑ n = 1 ∞ n 2 n s = ζ ( s − 2 ) {\displaystyle \operatorname {DG} \left(n^{2};s\right)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)}

Applications

Generating functions help us solve many types of problems in mathematics. They can be used to:

Find simple formulas for sequences defined by repeating rules, like the Fibonacci numbers.
Discover relationships between different sequences by comparing their generating functions.
Study how sequences grow or behave for very large numbers.
Prove mathematical statements about sequences.
Count combinations of objects in different ways, such as counting how many ways to arrange rooks on a chessboard.
Add up infinite series of numbers.

One example is using generating functions to find formulas for sums involving harmonic numbers, which are sums like 1 + 1/2 + 1/3 and so on. Another example is using them to work with binomial coefficients, which count ways to choose items from a group.

Generating functions can also help solve problems about tiling shapes with dominoes and understanding properties of sequences through convolutions, which combine sequences in specific ways.

Tables of special generating functions

An initial listing of special mathematical series is found here. Many useful and special sequence generating functions appear in Section 5.4 and 7.4 of Concrete Mathematics and in Section 2.5 of Wilf's Generatingfunctionology. The table below shows other special generating functions, but it is not a complete list.

Formal power series	Generating-function formula
∑ n = 0 ∞ ( m + n n ) ( H n + m − H m ) z n {\displaystyle \sum _{n=0}^{\infty }{\binom {m+n}{n}}\left(H_{n+m}-H_{m}\right)z^{n}}	1 ( 1 − z ) m + 1 ln ⁡ 1 1 − z {\displaystyle {\frac {1}{(1-z)^{m+1}}}\ln {\frac {1}{1-z}}}
∑ n = 0 ∞ B n z n n ! {\displaystyle \sum _{n=0}^{\infty }B_{n}{\frac {z^{n}}{n!}}}	z e z − 1 {\displaystyle {\frac {z}{e^{z}-1}}}
∑ n = 0 ∞ F m n z n {\displaystyle \sum _{n=0}^{\infty }F_{mn}z^{n}}	F m z 1 − ( F m − 1 + F m + 1 ) z + ( − 1 ) m z 2 {\displaystyle {\frac {F_{m}z}{1-(F_{m-1}+F_{m+1})z+(-1)^{m}z^{2}}}}
∑ n = 0 ∞ { n m } z n {\displaystyle \sum _{n=0}^{\infty }\left\{{\begin{matrix}n\\m\end{matrix}}\right\}z^{n}}	( z − 1 ) − m ¯ = z m ( 1 − z ) ( 1 − 2 z ) ⋯ ( 1 − m z ) {\displaystyle (z^{-1})^{\overline {-m}}={\frac {z^{m}}{(1-z)(1-2z)\cdots (1-mz)}}}
∑ n = 0 ∞ [ n m ] z n {\displaystyle \sum _{n=0}^{\infty }\left[{\begin{matrix}n\\m\end{matrix}}\right]z^{n}}	z m ¯ = z ( z + 1 ) ⋯ ( z + m − 1 ) {\displaystyle z^{\overline {m}}=z(z+1)\cdots (z+m-1)}
∑ n = 1 ∞ ( − 1 ) n − 1 4 n ( 4 n − 2 ) B 2 n z 2 n ( 2 n ) ⋅ ( 2 n ) ! {\displaystyle \sum _{n=1}^{\infty }{\frac {(-1)^{n-1}4^{n}(4^{n}-2)B_{2n}z^{2n}}{(2n)\cdot (2n)!}}}	ln ⁡ tan ⁡ ( z ) z {\displaystyle \ln {\frac {\tan(z)}{z}}}
∑ n = 0 ∞ ( 1 / 2 ) n ¯ z 2 n ( 2 n + 1 ) ⋅ n ! {\displaystyle \sum _{n=0}^{\infty }{\frac {(1/2)^{\overline {n}}z^{2n}}{(2n+1)\cdot n!}}}	z − 1 arcsin ⁡ ( z ) {\displaystyle z^{-1}\arcsin(z)}
∑ n = 0 ∞ H n ( s ) z n {\displaystyle \sum _{n=0}^{\infty }H_{n}^{(s)}z^{n}}	Li s ⁡ ( z ) 1 − z {\displaystyle {\frac {\operatorname {Li} _{s}(z)}{1-z}}}
∑ n = 0 ∞ n m z n {\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}}	∑ 0 ≤ j ≤ m { m j } j ! ⋅ z j ( 1 − z ) j + 1 {\displaystyle \sum _{0\leq j\leq m}\left\{{\begin{matrix}m\\j\end{matrix}}\right\}{\frac {j!\cdot z^{j}}{(1-z)^{j+1}}}}
∑ k	( 1 + 1 + 4 z 2 ) n + ( 1 − 1 + 4 z 2 ) n {\displaystyle \left({\frac {1+{\sqrt {1+4z}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {1+4z}}}{2}}\right)^{n}}
∑ n 1 , … , n m ≥ 0 min ( n 1 , … , n m ) z 1 n 1 ⋯ z m n m {\displaystyle \sum _{n_{1},\ldots ,n_{m}\geq 0}\min(n_{1},\ldots ,n_{m})z_{1}^{n_{1}}\cdots z_{m}^{n_{m}}}	z 1 ⋯ z m ( 1 − z 1 ) ⋯ ( 1 − z m ) ( 1 − z 1 ⋯ z m ) {\displaystyle {\frac {z_{1}\cdots z_{m}}{(1-z_{1})\cdots (1-z_{m})(1-z_{1}\cdots z_{m})}}}
∑ n = 0 ∞ ( s n ) z n {\displaystyle \sum _{n=0}^{\infty }{\binom {s}{n}}z^{n}}	( 1 + z ) s {\displaystyle (1+z)^{s}}
∑ n = 0 ∞ ( n k ) z n {\displaystyle \sum _{n=0}^{\infty }{\binom {n}{k}}z^{n}}	z k ( 1 − z ) k + 1 {\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}}
∑ n = 1 ∞ log ⁡ ( n ) z n {\displaystyle \sum _{n=1}^{\infty }\log {(n)}z^{n}}	− ∂ ∂ s L i s ( z ) \| s = 0 {\displaystyle \left.-{\frac {\partial }{\partial s}}\operatorname {{Li}_{s}(z)} \right\|_{s=0}}