Generating Functions and closed form

Question

I read somewhere that we can use generating functions to find closed form of a sequence. So what is the difference between a generating function and closed form of a sqeunce?

Answer 1

The generating function is a closed form of a power series that has (the closed form of) the terms of the sequence as its coefficients.

Generating function for sequence having terms $a_n$:

$$f(x) = \sum_{n=0}^{\infty} a_n x^n $$

Answer 2

Suppose that $\sigma=\langle a_n:n\in\Bbb N\rangle$ is a sequence of real numbers.

• A function $f:\Bbb N\to \Bbb R$ is a closed form for the $n$-th term of $\sigma$ if $f(n)=a_n$ for each $n\in\Bbb N$. (You can replace real with complex and $\Bbb R$ with $\Bbb C$, if you like.)

• The ordinary generating function for $\sigma$ is the function $g:\Bbb R\to\Bbb R$ or $g:\Bbb C\to\Bbb C$ whose power series expansion is $$g(x)=\sum_{n\in\Bbb N}a_nx^n\;.$$ In other words, the coefficient of $x^n$ in the power series expansion of $g(x)$ is the term $a_n$ of the sequence $\sigma$.

• The exponential generating function for $\sigma$ is the function $g:\Bbb R\to\Bbb R$ or $g:\Bbb C\to\Bbb C$ whose power series expansion is $$g(x)=\sum_{n\in\Bbb N}a_n\frac{x^n}{n!}\;.$$ In other words, the coefficient of $x^n$ in the power series expansion of $g$ is $\frac{a_n}{n!}$.

For example, let

$$g(x)=\frac1{1-x}=\sum_{n\ge 0}x^n\;;\tag{1}$$

the coefficient of $x^n$ in this power series is $1$ for every $n\in\Bbb N$, so the function $g$ is the ordinary generating function for the constant sequence $\langle 1,1,1,\ldots\rangle$. The closed form of the $n$-th term of this sequence, however, is simply $a_n=1$, or in functional notation $f(n)=1$.

However, we can rewrite the series in $(1)$ as

$$\frac1{1-x}=\sum_{n\ge 0}n!\left(\frac{x^n}{n!}\right)\;,$$

so this same function $g(x)=\dfrac1{1-x}$ is also the exponential generating function of the sequence $\langle n!:n\in\Bbb N\rangle$. The closed form of this sequence is $a_n=n!$, or in functional notation $f(n)=n!$.

If we differentiate $(1)$, we get

$$g'(x)=\frac1{(1-x)^2}=\sum_{n\ge 0}nx^{n-1}=\sum_{n\ge 0}(n+1)x^n\;,$$

so the function $g'$ is the ordinary generating function of the sequence $$\langle n+1:n\in\Bbb N\rangle=\langle 1,2,3,\ldots\rangle\;.$$ This sequence has closed form $a_n=n+1$, or in functional notation $f(n)=n+1$.

Answer 3

For the sequence $\langle a_n \rangle$ the (ordinary) generating function is $A(z) = \sum_{n \ge 0} a_n z^n$ (you get other flawors of generating functions by selecting some other sequence of functions instead of $z^n$ to mark the positions). The point of generating functions is that they summarize the whole sequence in a single object (Wilf's "generatingfunctionology" explains this by saying that the generating function is a clothes line on which you hang the coefficients for exhibition). Certain common operations on the sequences (e.g. summing term by term) translate into simple operations on the generating functions (adding), for more details look at the cited book. Translating a problem into generating functions allows to use the sophisticated tools of algebra and calculus to discrete problems, and often provides simple solutions to otherwise mysterious situations. Sometimes from the generating function one can extract a closed form for the terms of the sequence. Even in case this isn't possible, calculus offers techniques to derive asymptotic behaviour. Even when a closed form is available, a simple asymptotic estimate might be preferable.