Preface

This section gives an introduction to generating functions that give sometime a compact expression that, when expanded into series, has coefficients to be the given sequence. They were invented by the French mathematician Abraham de Moivre (1667--1754) in the early eighteen century. However, it was Leonhard Euler (1707--1783) who had extensive applications in discrete mathematics.

Return to computing page for the first course APMA0330
Return to computing page for the second course APMA0340
Return to Mathematica tutorial for the first course APMA0330
Return to Mathematica tutorial for the second course APMA0340
Return to the main page for the course APMA0330
Return to the main page for the course APMA0340
Return to Part V of the course APMA0330

Glossary

Generating functions

The time has come to introduce the most powerful mathematical tool--generating functions. They provide a natural and elegant way to deal with sequences of numbers by associating a function of a continuous variable with a sequence. In this way generating functions provide a bridge between discrete and continuous mathematics. They were invented by Abrahan de Moivre (1667--1754) in the early eighteenth century and like much of discrete mathematics, came to prominence through the work of Leonhard Euler (1707--1783) in the middle of that century.

In what follows, we will use the summation notation, which not only reduces the labor involved, but is often helpful in recognizing the general term of the series. According to the notation, a series such as

\[ a_0 + a_1 + a_2 + \cdots + a_n \]
with a finite number of terms is represented by
\[ \sum_{i=0}^n a_i \qquad \mbox{or} \qquad \sum_{0\le j \le n} a_j \qquad \mbox{or} \qquad \sum_{k\in [0..n]} a_k . \]
The sign Σ is a Greek capital letter sigma, i, j, or k is called the summation index, which take consecutive integer values. Note that since the latter is the dummy index, any letter or character can be used for the index. The value i = 0 is referred to as the lower limit, while i = n is referred to as the upper limit. The term 𝑎j is known as the general term.

An infinite series has an infinite number of terms and an upper limit of infinity. It is denoted as

\[ \sum_{i=0}^{\infty} a_i \qquad \mbox{or} \qquad \sum_{j \ge 0} a_j , \]
An expression of the form
\[ \sum_{n=0}^{\infty} a_n \left( x - x_0 \right)^n = \sum_{n\ge 0} a_n \left( x - x_0 \right)^n = a_0 + a_1 \left( x - x_0 \right) + a_2 \left( x - x_0 \right)^2 + a_3 \left( x - x_0 \right)^3 + \cdots , \]
in which the 𝑎n are real or complex constants, is called a power series in x - x0 .

A sequence is a denumerable set 𝑎n, n = 0,1,2, …, of real or complex numbers in a specific order. The value of 𝑎n can behave in a variety of ways as n → ∞; for instance, 𝑎n = 1/n, n = 1,2, …. The starting index is usually zero or one, but for Mathematica it does not matter and it allows to start with any number. There are several ways to associate a function with a sequence { 𝑎n }n≥0, that we will always enumerate starting with zero. We present two the most popular definitions of a generating function.

Let \( \{ a_n \}_{n\ge 0} \) be a sequence of numbers. Then, the formal power series
\[ a(z) = \sum_{n\ge 0} a_n z^n \]
is the ordinary generating function of the sequence \( {\bf a} = \{ a_n \}_{n\ge 0} . \) Another power series
\[ A(z) = \sum_{n\ge 0} a_n \,\frac{z^n}{n!} \]
is called the exponential generating function for the sequence a.

These two generating functions are related via the Laplace--Borel transform (also called Sumudu transform):
\[ a(z) = \int_0^{\infty} A\left( zt \right) e^{-t} {\text d}t . \]
The inverse operation is called extracting of coefficients.
Let \( f(z) = \sum_{n\ge 0} a_n z^n \) be a power series in variable z. Then the symbol \( \left[ z^n \right] f(z) \) stands for the coefficient of zn in the power series expansion, which is 𝑎n. This operation is called extraction of the coefficients. Whenever the differentiation is possible, \( \left[ z^n \right] f(z) = \left. \frac{{\text d^n}}{{\text d}z^n} \,f(z) \right\vert_{z=0} . \)

Although convergence plays no role in the generating-function method, which deals with formal power series, when convergence occurs and infinite sums are known, this additional information may be useful in actual calculations. It is always fruitful to have a closed form formula for an infinite sum, however, it depends on the definition of convergence, which we discuss in a special section. An ordinary generating function converges only when the coefficients of the sequence grow no faster than polynomial growth. On the other hand, exponential generating functions converge for sequences that grow faster than polynomials, including some exponential growth. Therefore, calculus of exponential functions is wider in scope than that of ordinary generating functions. Moreover, exponential generating functions resemble Maclaurin power series that will be our main topic in next sections devoted to series solutions of differential equations.

The importance of generating functions is based on the correspondence between operations on sequences and their generating functions. We collect some basic properties of ordinary and exponential generating functions that are presented in the following tables.

Rule Sequence element 𝑎n Ordinary generating function
Definition { 𝑎n }n≥ 0 \( a(z) = \sum_{n\ge 0} a_n z^n \)
Scaling k 𝑎n k 𝑎(z)
Addition { 𝑎n } + { bn } \( a(z) + b(z) = \sum_{n\ge 0} \left( a_n + b_n \right) z^n \)
Right Shifting by 1 𝑎n+1 \( \displaystyle \frac{a(z) - a_0}{z} \)
Right Shifting 𝑎n+k \( \displaystyle \frac{a(z) - a_0 - \cdots - a_{k-1}z^{k-1}}{z^k} \)
Left shift cn = 𝑎n-1 z 𝑎(z) + c0
Convolution \( \displaystyle \left( {\bf a} \ast {\bf b} \right)_n = \sum_k a_k b_{n-k} \) 𝑎(z) 𝑎b(z)
Multiplication by n n𝑎n \( \displaystyle z\,\frac{\text d}{{\text d}z}\,a(z) = z\,{\texttt D}\,a(z) \)
Division by n \( \displaystyle \frac{a_n}{n} \) \( \displaystyle c_0 + \int_0^z \frac{a(t) - a_0}{t}\,{\text d}t \)
Sum first n terms \( \displaystyle a_0 + a_1 + \cdots + a_n \) \( \displaystyle \frac{a(z)}{1-z} \)
Multiplication and right shift (n+1) 𝑎n+1 \( \displaystyle \frac{\text d}{{\text d}z}\, a(z) = {\texttt D}\,a(z) \)
Multiplication and left shift n 𝑎n-1 \( \displaystyle \left( z^2 {\texttt D}^2 + z \right) a(z) \)

 

Exponential generating functions:

 

Rule Sequence element 𝑎n Exponential generating function
Definition { 𝑎n }n≥ 0 \( A(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \)
Scaling k 𝑎n \( \displaystyle k\,A(z) = \sum_{n\ge 0} k\,a_n \frac{z^n}{n!} \)
Addition { 𝑎n } + { bn } \( \displaystyle A(z) + B(z) = \sum_{n\ge 0} \left( a_n + b_n \right) \frac{z^n}{n!} \)
Right Shifting by 1 𝑎n+1 \( \displaystyle A'(z) = \frac{\text d}{{\text d}z}\, A(z) \)
Right Shifting 𝑎n+k \( \displaystyle A^{(k)}(z) = \frac{{\text d}^k}{{\text d}z^k}\, A(z) \)
Left shift by 1 cn = 𝑎n-1 \( \displaystyle \int A(z)\,{\text d}z \)
Multiplication by nk nk 𝑎n \( \displaystyle \left( z\,{\texttt D} \right)^k A(z) \)
Multiplication by n and left shift n𝑎n-1 z A(z)
Binomial convolution \( \displaystyle \sum_k \binom{k}{n} a_k b_{n-k} \) \( \displaystyle A(z)\,B(z) \)
Right shift and division \( \displaystyle \frac{a_{n+1}}{n+1} \) \( \displaystyle \frac{A(z) - A(0)}{z} \)
Multiplication and right shift (n+1) 𝑎n+1 \( \displaystyle {\texttt D}\,z\,{\texttt D}\,A(z) \)
Multiplication and right shift n 𝑎n+1 \( \displaystyle z\,{\texttt D}^2 A(z) \)

Example: The ordinary generating function of the famous Catalan numbers Cn is

\[ C(z) = \frac{1- \sqrt{1-4z}}{2z} = \sum_{n\ge 0} C_n \,z^n , \qquad C_n = \frac{1}{n+1} \binom{2n}{n} . \]
They are named after the Belgian mathematician Eugène Charles Catalan (1814--1894). Catalan numbers were invented by Leonhard Euler in 18th century.

Example: The exponential generating function of the famous Bell numbers Bn is

\[ \hat{\cal B}(z) = e^{e^z -1} = \sum_{n\ge 0} {\cal B}_n \,\frac{z^n|}{n!} , \qquad {\cal B}_n = \frac{1}{e}\,\sum_{k=0}^n \frac{k^n}{k!} . \]
They are named after Eric Temple Bell, who wrote about them in the 1930s.

Example: Consider the function

\[ f(x) = 2\,\sin (x) -3\,\arcsin (x) . \]
f[x_] := 2*Sin[x] + 2*ArcSin[x]
We expand this function into the Taylor series about 0:
ser = Series[f[x], {x, 0, 14}]
\[ 4x + \frac{x^5}{6} -\frac{4\, x^7}{45} + \frac{5513\, x^9}{90720} + \frac{2537\, x^{11}}{56700} - \frac{4156001\,x^{13}}{119750400} + O\left( x^{15} \right) \]
The 0 indicates that the series is centered about 0 (such series are often called Maclaurin series) and the 14 specifies the highest power sought. The Series command gives its output in a special form, with a big-Oh error term. If only the partial sum of the series is wanted, then use Normal:
Normal[ser]
There is a coincidental cancellation of the third-degree terms when sine and arcsine are added, and the function is close to being linear. The contribution of the fifth- and higher-order terms, whose coefficients are rather small on the interval [-1, 1], is very small.

 

  1. Dobrushkin, V.A., Methods in Algorithmic Analysis, CRC Press, Boca Raton, FL, 2009.
  2. Niven, I., Formal Power Series, The American Mathematical Monthly, 1969, Vol. 76, No. 8, pp. 871--889.

 

Return to Mathematica page
Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value Problems)