Editing Generating function (section)

=== Examples for simple sequences ===

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 fundamental generating function is that of the constant sequence {{nowrap|1, 1, 1, 1, 1, 1, 1, 1, 1, ...}}, whose ordinary generating function is the [[Geometric_series#Closed-form_formula|geometric series]]
<math display="block">\sum_{n=0}^\infty x^n= \frac{1}{1-x}.</math>

The left-hand side is the [[Maclaurin series]] expansion of the right-hand side. Alternatively, the equality can be justified by multiplying the power series on the left by {{math|1 − ''x''}}, and checking that the result is the constant power series 1 (in other words, that all coefficients except the one of {{math|''x''<sup>0</sup>}} are equal to 0). Moreover, there can be no other power series with this property. The left-hand side therefore designates the [[multiplicative inverse]] of {{math|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 {{math|''x'' → ''ax''}} gives the generating function for the [[Geometric progression|geometric sequence]] {{math|1, ''a'', ''a''<sup>2</sup>, ''a''<sup>3</sup>, ...}} for any constant {{mvar|a}}:
<math display="block">\sum_{n=0}^\infty(ax)^n= \frac{1}{1-ax}.</math>

(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,
<math display="block">\sum_{n=0}^\infty(-1)^nx^n= \frac{1}{1+x}.</math>

One can also introduce regular gaps in the sequence by replacing {{mvar|x}} by some power of {{mvar|x}}, so for instance for the sequence {{nowrap|1, 0, 1, 0, 1, 0, 1, 0, ...}} (which skips over {{math|''x'', ''x''<sup>3</sup>, ''x''<sup>5</sup>, ...}}) one gets the generating function
<math display="block">\sum_{n=0}^\infty x^{2n} = \frac{1}{1-x^2}.</math>

By squaring the initial generating function, or by finding the derivative of both sides with respect to {{mvar|x}} and making a change of running variable {{math|''n'' → ''n'' + 1}}, one sees that the coefficients form the sequence {{nowrap|1, 2, 3, 4, 5, ...}}, so one has
<math display="block">\sum_{n=0}^\infty(n+1)x^n= \frac{1}{(1-x)^2},</math>

and the third power has as coefficients the [[triangular number]]s {{nowrap|1, 3, 6, 10, 15, 21, ...}} whose term {{mvar|n}} is the [[binomial coefficient]] {{math|{{pars|s=150%|{{su|p=''n'' + 2|b=2|a=c}}}}}}, so that
<math display="block">\sum_{n=0}^\infty\binom{n+2}2 x^n= \frac{1}{(1-x)^3}.</math>

More generally, for any non-negative integer {{mvar|k}} and non-zero real value {{mvar|a}}, it is true that
<math display="block">\sum_{n=0}^\infty a^n\binom{n+k}k x^n= \frac{1}{(1-ax)^{k+1}}\,.</math>

Since
<math display="block">2\binom{n+2}2 - 3\binom{n+1}1 + \binom{n}0 = 2\frac{(n+1)(n+2)}2 -3(n+1) + 1 = n^2,</math>

one can find the ordinary generating function for the sequence {{nowrap|0, 1, 4, 9, 16, ...}} of [[square number]]s by linear combination of binomial-coefficient generating sequences:
<math display="block">G(n^2;x) = \sum_{n=0}^\infty n^2x^n = \frac{2}{(1-x)^3} - \frac{3}{(1-x)^2} + \frac{1}{1-x} = \frac{x(x+1)}{(1-x)^3}.</math>

We may also expand alternately to generate this same sequence of squares as a sum of derivatives of the [[geometric series]] in the following form:
<math display="block">\begin{align}
G(n^2;x)
 & = \sum_{n=0}^\infty n^2x^n \\[4px]
 & = \sum_{n=0}^\infty n(n-1) x^n + \sum_{n=0}^\infty n x^n \\[4px]
 & = x^2 D^2\left[\frac{1}{1-x}\right] + x D\left[\frac{1}{1-x}\right] \\[4px]
 & = \frac{2 x^2}{(1-x)^3} + \frac{x}{(1-x)^2} =\frac{x(x+1)}{(1-x)^3}.
\end{align}</math>

By induction, we can similarly show for positive integers {{math|''m'' ≥ 1}} that<ref>{{cite journal|first1= Michael Z. | last1=Spivey | title=Combinatorial Sums and Finite Differences | year=2007 |journal = Discrete Math. |doi = 10.1016/j.disc.2007.03.052 | volume=307|number=24|pages=3130–3146|mr=2370116|doi-access=free }}</ref><ref>{{cite arXiv|first1=R. J. |last1=Mathar|year=2012|eprint=1207.5845|title=Yet another table of integrals|class=math.CA}} v4 eq. (0.4)</ref>
<math display="block">n^m = \sum_{j=0}^m \begin{Bmatrix} m \\ j \end{Bmatrix} \frac{n!}{(n-j)!}, </math>

where {{math|{{resize|150%|{}}{{su|p=''n''|b=''k''}}{{resize|150%|}<nowiki/>}}}} denote the [[Stirling numbers of the second kind]] and where the generating function
<math display="block">\sum_{n = 0}^\infty \frac{n!}{ (n-j)!} \, z^n = \frac{j! \cdot z^j}{(1-z)^{j+1}},</math>

so that we can form the analogous generating functions over the integral {{mvar|m}}th powers generalizing the result in the square case above. In particular, since we can write
<math display="block">\frac{z^k}{(1-z)^{k+1}} = \sum_{i=0}^k \binom{k}{i} \frac{(-1)^{k-i}}{(1-z)^{i+1}},</math>

we can apply a well-known finite sum identity involving the [[Stirling numbers]] to obtain that<ref>{{harvnb|Graham|Knuth|Patashnik|1994|loc=Table 265 in §6.1}} for finite sum identities involving the Stirling number triangles.</ref>
<math display="block">\sum_{n = 0}^\infty n^m z^n = \sum_{j=0}^m \begin{Bmatrix} m+1 \\ j+1 \end{Bmatrix} \frac{(-1)^{m-j} j!}{(1-z)^{j+1}}. </math>