13
$\begingroup$

I am having introductory lectures on combinatorial analysis, I've been presented to the concept of generating functions and it's applications to solving combinatorial problems. The generating function of the sequence $(1,1,1,1,1,1,\ldots)$ is:

$$1+x+x^2+x^3+x^4+x^5+\ldots\tag{1}$$

Which can be reduce to a closed form expression:

$$\displaystyle\frac{1}{1-x}\tag{2}$$

But until the present moment, the exercises I made in the chapters we're studying asked us to write $(1)$ as $(2)$, there wasn't anything about using the closed form to obtain further results. In the combinatorial exercises I made, I had only to evaluate the coefficient of a certain term in the generating function or the exponent of a certain coefficient in the formal series and at least in the book I'm using, there is still no use to the closed form of certain formal power series.

So why is it important to have a closed form such as $(2)$? I still don't get why it is important/useful.

$\endgroup$
1
  • 2
    $\begingroup$ you have two sequences (and it's gfs) - A and B and you'd like to convolute them (also known as Cauchy product). Multiple this gfs closed forms and you're done - now you can convert it to first form. For more check: math.upenn.edu/~wilf/DownldGF.html $\endgroup$
    – fex
    Jan 6, 2015 at 13:24

1 Answer 1

18
$\begingroup$

There are many reasons. Here are some:

  1. Closed forms facilitate calculations with generating functions. Certain combinatorial operations correspond to simple operations on the generating functions such as addition and multiplication, and these are facilitated by working with closed forms.

  2. Proving identities. Continuing the previous bullet, manipulations of generating functions leading to the zero function correspond to a combinatorial identity stating that matching coefficients are equal. This is important for automated methods for proving combinatorial identities, such as the ones described in the book A=B. Other examples are proofs of certain identities regarding the partition function, and one proof of the four square theorem.

  3. Extracting coefficients. As you mention, if you just take a given sequence and transform it into a generating function, this seems pointless. But sometimes generating functions can result from solving equations – the classical example is the Fibonacci sequence. Or they could result from manipulations as described in the first bullet. There are techniques, such as partial fraction decomposition, to extract coefficients from generating functions, and they can be used to find formulas for recurrence sequences.

  4. Asymptotic analysis. Probably the most important reason to use generating functions is that they allow the use of analytic methods to determine the order of growth of the coefficients, using various techniques. An offshoot of this approach is the method of characteristic functions in probability theory.

$\endgroup$
1
  • 2
    $\begingroup$ A side consideration is simply that it is a general mathematical style that finite is desired more than the infinite. You have a better handle on things if they have been reduced to a finite thing. Ellipses are a sign of inscrutability. Of course, with notation, ellipses can be encapsulated into symbols with iteration, and then progress is measured in terms of reduction in bound variables (removing the iteration). Sure a gf can be more inscrutable, but part of math is having multiple formalisms to operate on. That's general strategy. Yuval's excellent answer gives specifics for ops on gfs. $\endgroup$
    – Mitch
    Jan 6, 2015 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .