Basic Notation and Terminology

With a sequence \(\sigma=\{a_n:n\ge0\}\) of real numbers, we associate a function \(F(x)\) defined by \[\begin{aligned}\end{aligned}\] The word function is put in quotes as we do not necessarily care about substituting a value of \(x\) and obtaining a specific value for \(F(x)\). In other words, we consider \(F(x)\) as a formal power series and frequently ignore issues of convergence.

It is customary to refer to \(F(x)\) as the generating function of the sequence \(\sigma\). As we have already remarked, we are not necessarily interested in calculating \(F(x)\) for specific values of \(x\). However, by convention, we take \(F(0)=a_0\).

The method of can be adapted to address the finite geometric series \(\sum_{j=0}^n x^j\). In that case, we look at \[\begin{aligned}(1-x) \sum_{j=0}^nx^j \amp= \sum_{j=0}^n x^j - \sum_{j=0}^n x^{j+1} \\ \amp= (1+x+\cdots + x^n) - (x+x^2+\cdots x^n + x^{n+1})\end{aligned}\]. Looking carefully, we see that everything cancels in the final expression except \(1-x^{n+1}\). Dividing both sides by \(1-x\) gives us \[\begin{aligned}\end{aligned}\] as the formula for the sum of a finite geometric series.

For reference, we state the following elementary result, which emphasizes the form of a product of two power series.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.