Ordinary Generating Functions
Polynomials are a special case of ordinary generating functions, corresponding to finite sequences, or equivalently sequences that vanish after a certain point. These are important in that many finite sequences can usefully be interpreted as generating functions, such as the Poincaré polynomial, and others.
A key generating function is the constant sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., whose ordinary generating function is
The left-hand side is the Maclaurin series expansion of the right-hand side. Alternatively, the right-hand side expression can be justified by multiplying the power series on the left by 1 − x, and checking that the result is the constant power series 1, in other words that all coefficients except the one of x0 vanish. Moreover there can be no other power series with this property. The left-hand side therefore designates the multiplicative inverse of 1 − x in the ring of power series.
Expressions for the ordinary generating function of other sequences are easily derived from this one. For instance, the substitution x → ax gives the generating function for the geometric sequence 1,a,a2,a3,... for any constant a:
(The equality also follows directly from the fact that the left-hand side is the Maclaurin series expansion of the right-hand side.) In particular,
One can also introduce regular "gaps" in the sequence by replacing x by some power of x, so for instance for the sequence 1, 0, 1, 0, 1, 0, 1, 0, .... one gets the generating function
By squaring the initial generating function, or by finding the derivative of both sides with respect to x and making a change of running variable n → n-1, one sees that the coefficients form the sequence 1, 2, 3, 4, 5, ..., so one has
and the third power has as coefficients the triangular numbers 1, 3, 6, 10, 15, 21, ... whose term n is the binomial coefficient, so that
More generally, for any positive integer k, it is true that
Note that, since
one can find the ordinary generating function for the sequence 0, 1, 4, 9, 16, ... of square numbers by linear combination of binomial-coefficient generating sequences;
Read more about this topic: Generating Function
Famous quotes containing the words ordinary and/or functions:
“Marriage was contrived for ordinary people, for people who are capable of neither great love nor great friendship, which is to say, for most peoplebut also for those exceptionally rare ones who are capable of love as well as of friendship.”
—Friedrich Nietzsche (18441900)
“One of the most highly valued functions of used parents these days is to be the villains of their childrens lives, the people the child blames for any shortcomings or disappointments. But if your identity comes from your parents failings, then you remain forever a member of the child generation, stuck and unable to move on to an adulthood in which you identify yourself in terms of what you do, not what has been done to you.”
—Frank Pittman (20th century)