In this post we will discuss generating functions. Generating functions are a powerful tool which can be used to solve many problems both in combinatorics and also in analysis.
Let denote the set of all sequences of real numbers. For all we let denote the sequence which has value for its th term and all its other terms are zero. The symbol 1 stands for the sequence . Also for any real number we define the product of and a sequence as . We let two sequences and be equal if for all . We define the sum of and by the sequence and the product by the sequence where . Clearly the sequence is equal to the sequence which we will also denote simply by . Note that here stands for the sequence obtained as a product of and 1, i.e. . Algebraically speaking , equipped with these operations, is an -algebra.
More importantly there is an analytic viewpoint of also. Readers who are familiar with the theory of power series can consider the elements of to be power series, i.e. each element is basically a function with its domain an open interval (or simply ). By standard theorems in analysis, if and both converge for then for all such , if and only if for all $i$. Hence the approach of considering as a purely formal object may be considered equivalent to considering it as a power series.
However, we will soon see as to why convergence issues do not play any role in our context as long as the power series converges for at least one non zero and there is more value in interpreting as simply an element of .
Let be a real sequence such that the power series converges for at least one non zero . Then the function which sends such an to the power series is called the generating function of the sequence. We frequently abuse notation and refer to the value of the generating function at some non-zero point as the generating function (which is akin to referring the function as ).
Let be the constant sequence of one’s. It is well known that for any real number , if the series converges to . So the generating function of is where for all at which the series converges.
The reason for requiring convergence at a non zero point is as follows. As soon as we have convergence at a non zero , by a theorem of analysis it follows that there is convergence in an open interval around . Now, has a unique power series expansion in that interval and so we are guaranteed that there is a one-one correspondence between the purely discrete object thought of as an element of and the generating function . This can be exploited in the reverse direction, for if we wish to recover our sequence from the function , then since is defined by there is absolutely no ambiguity, and we cannot get back any other sequence. In fact, we may say that our sequence has been encoded within the definition of , as a closed form expression .
If convergence was only given at , then such a one-one correspondence is not possible, since any closed form analytic function , which is at would become the generating function to the sequence . So for any sequence we will consider its generating function to be defined by as long as there is a non zero $x$ for which there is convergence, and once we have done that will not bother about any convergence issues at all.
The reader may be wondering what was the point of giving an algebraic approach initially, for a generating function really seems to have to do more with a power series. Furthermore in the notation of the first paragraph when we were considering a sequence as an element of we gave found that in our algebra is nothing but . This was not a power series but simply our notation for a sequence. It may appear confusing to have the same notation for two different objects, but it has been deliberately adopted for a very good reason. During our computations, we often manipulate our series so that we may no longer be sure whether convergence of a given series at a non-zero point is guaranteed. This poses a mathematical problem of the validity of our operations. However our ambiguous notation comes to our rescue at that instant, for what we really are doing at that point, without explicitly saying so, is not dealing with the series . Instead we are manipulating the sequence with which there are absolutely no concepts of convergence attached. Of course if we need closed form expressions or some other analytic properties have to be established we need convergence so that one can use the one-one correspondence between the sequence and the generating function and dive in the world of analysis. In this way, a constant interplay between the discrete world of sequences and the analytic world of sequences brings out the real power of generating functions.