Generating function

In mathematics, a generating function is a special way to represent an infinite sequence of numbers. It uses the numbers as the coefficients in a math expression called a formal power series. Often, we can 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.

Generating functions are also called generating series because the series can create 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 number pattern problems.

Later, Laplace named them "generating functions." Before that, Euler used similar ideas to solve problems in combinatory analysis and number theory.

Definition

A generating function is like a special bag for numbers. Instead of listing numbers one by one, we put them inside this bag. This helps us work with the numbers more easily.

Two famous mathematicians talked about this idea. George Pólya said it’s like carrying many little objects in one bag. Herbert Wilf compared it to hanging numbers on a clothesline for display.

Generating functions use special math expressions to represent sequences of numbers. These expressions are used to organize numbers in a neat way. They look like normal math functions but are used differently 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 an 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.

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.

Ordinary generating functions

Examples for simple sequences

Polynomials are a special type of ordinary generating function. They match finite sequences. Many finite sequences can work as generating functions, like the Poincaré polynomial.

A basic generating function is for the constant sequence 1, 1, 1, 1, and so on. Its ordinary generating function is the geometric series ∑ₙ=₀^∞ xⁿ = 1/(1−x). The left side is the Maclaurin series of the right side. You can also check this by multiplying the power series on the left by 1−x and see that it gives the constant series 1.

You can find generating functions for other sequences from this one. For example, replacing x with ax gives the generating function for the geometric sequence 1, a, a², a³, and so on: ∑ₙ=₀^∞ (ax)ⁿ = 1/(1−ax).

You can also create gaps in the sequence by using a power of x. For the sequence 1, 0, 1, 0, 1, 0, 1, 0, and so on, the generating function is ∑ₙ=₀^∞ x²ⁿ = 1/(1−x²).

By squaring the first generating function, or by taking the derivative of both sides and adjusting the index n → n + 1, we find that the coefficients match the sequence 1, 2, 3, 4, 5, and so on. This gives ∑ₙ=₀^∞ (n + 1) xⁿ = 1/(1−x)². The third power has coefficients that are triangular numbers 1, 3, 6, 10, 15, 21, and so on. The nth term is the binomial coefficient (n+2 choose 2), so ∑ₙ=₀^∞ (n+2 choose 2) xⁿ = 1/(1−x)³.

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

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

We can also get this sequence of squares by adding together derivatives of the geometric series: 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 written as a rational function (the ratio of two polynomials) if and only if the sequence follows a linear recursive sequence with fixed steps. This includes the examples above. Conversely, every sequence from a fraction of polynomials follows a linear pattern with fixed steps.

We also see that rational generating functions match sequences of the form fₙ = p₁(n)ρ₁ⁿ + ⋯ + p_ℓ(n)ρ_ℓⁿ, where the values ρᵢ ∈ ℂ are fixed, and pᵢ(n) is a polynomial in n for all 1 ≤ i ≤ ℓ.

Operations on generating functions

Multiplication yields convolution

Multiplying ordinary generating functions gives a discrete convolution (the Cauchy product) of the sequences.

Shifting sequence indices

For integers m ≥ 1, we have these identities for the changed generating functions of the shifted sequences ⟨gₙ−m⟩ and ⟨gₙ+m⟩.

Differentiation and integration of generating functions

We have these series for the first derivative of a generating function and its integral:

The differentiation–multiplication operation can be repeated k times to multiply the sequence by nᵏ, but this needs switching between differentiation and multiplication. If you do k derivations in a row, it multiplies by the kth falling factorial.

Using the Stirling numbers of the second kind, this can be turned into another way to multiply by nᵏ.

Enumerating arithmetic progressions of sequences

Here we give formulas for generating functions that list the sequence {fₐₙ₊b} from an ordinary generating function F(z), where a ≥ 2, 0 ≤ b.

Properties of the hth convergent functions

For h ≥ 0 (but usually h ≥ 2), we can define the rational hth convergents to the endless J-fraction, J^∞, expanded by: Convₕ(z) := Pₕ(z)/Qₕ(z) = j₀ + j₁z + ⋯ + j₂ʰ−₁z²ʰ−¹ + ∑ₙ=₂ʰ^∞ j̃ₕ,ₙzⁿ through the sequences, Pₕ(z) and Qₕ(z), defined by steps.

Examples

The next table gives examples of closed-form formulas for the sequences found by computation (and later proven right) in special cases of the sequences, jₙ, made by the general rules of the J-fractions from the first part. 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 areas where these series end for the Jacobi-type J-fractions are usually different from the areas for the ordinary generating functions of these sequences.

Examples

Square numbers

Generating functions can help us study sequences like square numbers, where each term is n². These functions connect to important math 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 math problems. They can be used to:

Find easy formulas for sequences that follow rules, like the Fibonacci numbers.
Learn how different sequences are related by comparing their generating functions.
Study how sequences change when the numbers get really big.
Prove ideas about sequences.
Count different ways to arrange objects, such as counting how many ways to place rooks on a chessboard.
Add up endless series of numbers.

One example is using generating functions to find formulas for sums with 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 puzzles about covering shapes with dominoes and understanding sequences by combining them in special ways.

Tables of special generating functions

You can find a list of special mathematical series here. Many useful generating functions are in Section 5.4 and 7.4 of Concrete Mathematics and in Section 2.5 of Wilf's Generatingfunctionology. The table below shows more special generating functions, but it is not a full 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}}