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 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
An infinite series has an infinite number of terms and an upper limit of infinity. It is denoted as
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.
These two generating functions are related via the Laplace--Borel transform (also called Sumudu transform):
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} } + { b_{n} } | \( 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 | c_{n} = 𝑎_{n-1} | z 𝑎(z) + c_{0} |
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} } + { b_{n} } | \( \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 | c_{n} = 𝑎_{n-1} | \( \displaystyle \int A(z)\,{\text d}z \) |
Multiplication by n^{k} | n^{k} 𝑎_{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 C_{n} is
Example: The exponential generating function of the famous Bell numbers B_{n} is
Example: Consider the function
- Dobrushkin, V.A., Methods in Algorithmic Analysis, CRC Press, Boca Raton, FL, 2009.
- 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)