8.1: Basic Notation and Terminology
- Page ID
- 97907
With a sequence \(\sigma=\{a_n:n \geq 0\}\) of real numbers, we associate a “function” \(F(x)\) defined by
\(F(x) = \displaystyle \sum_{n=0}^{\infty} a_nx^n\).
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\).
Consider the constant sequence \(\sigma=\{a_n:n \geq 0\} \)with \(a_n=1\) for every \(n \geq 0\). Then the generating function \(F(x)\) of \(\sigma\) is given by
\(F(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + \cdot \cdot \cdot\),
which is called the infinite geometric series.
You may remember that this last expression is the Maclaurin series for the function \(F(x)=1/(1−x)\) and that the series converges when \(|x|<1\). Since we want to think in terms of formal power series, let's see that we can justify the expression
\(\dfrac{1}{1-x} = 1+x+x^2+x^3+x^4+x^5+x^6+ \cdot \cdot \cdot = \displaystyle \sum_{n=0}^{\infty} x^n\)
without any calculus techniques. Consider the product
\((1-x)(1+x+x^2+x^3+x^4+x^5+x^6+ \cdot \cdot \cdot)\)
and notice that, since we multiply formal power series just like we multiply polynomials (power series are pretty much polynomials that go on forever), we have that this product is
\((1+x+x^2+x^3+x^4+x^5+x^6+ \cdot \cdot \cdot) - x(1+x+x^2+x^3+x^4+x^5+x^6+ \cdot \cdot \cdot) = 1\).
Now we have that
\((1-x)(1+x+x^2+x^3+x^4+x^5+x^6+ \cdot \cdot \cdot) = 1\),
or, more usefully, after dividing through by \(1-x\),
\(\dfrac{1}{1-x} = \displaystyle \sum_{n=0}^{\infty} x^n\).
The method of Example 8.1 can be adapted to address the finite geometric series \(\sum_{j=0}^n x^j\). In that case, we look at
\((1-x) \displaystyle \sum_{j=0}^n x^j = \sum_{j=0}^n x^j - \sum_{j=0}^n x^{j+1}\)
\((1+x+ \cdot \cdot \cdot + x^n) - (x + x^2 + \cdot \cdot \cdot x^n + x^{n+1})\).
Looking carefully, we see that everying cancels in the final expression except \(1−x^{n+1}\). Dividing both sides by \(1−x\) gives us
\(1+x+ \cdot \cdot \cdot + x^n = \dfrac{1-x^{n+1}}{1-x}\)
as the formula for the sum of a finite geometric series.
Just like you learned in calculus for Maclaurin series, formal power series can be differentiated and integrated term by term. The rigorous mathematical framework that underlies such operations is not our focus here, so take us at our word that this can be done for formal power series without concern about issues of convergence.
To see this in action, consider differentiating the power series of the previous example. This gives
\(\dfrac{1}{(1-x)^2} = 1+2x+3x^2+4x^3+5x^4+6x^5+7x^6+ \cdot \cdot \cdot = \displaystyle \sum_{n=1}^{\infty} nx^{n-1}\).
Integration of the series represented by \(1/(1+x)=1/(1−(−x))\) yields (after a bit of algebraic manipulation)
\(\log(1+x) = x - \dfrac{x^2}{2} + \dfrac{x^3}{3} - \dfrac{x^4}{4} + \dfrac{x^5}{5} - \dfrac{x^6}{6} + \cdot \cdot \cdot = \displaystyle \sum_{n=1}^{\infty}(-1)^{n+1} \dfrac{x^n}{n}\).
Before you become convinced that we're only going to concern ourselves with generating functions that actually converge, let's see that we can talk about the formal power series
\(F(x) = \displaystyle \sum_{n=0}^{\infty}n!x^n\),
even though it has radius of convergence 0, i.e., the series \(F(x)\) converges only for \(x=0\), so that \(F(0)=1\). Nevertheless, it makes sense to speak of the formal power series \(F(x)\) as the generating function for the sequence \(\{a_n:n \geq 0\}\), \(a_0=1\) and \(a_n\) is the number of permutations of \(\{1,2,…,n\}\) when \(n \geq 1\).
For reference, we state the following elementary result, which emphasizes the form of a product of two power series.
Let \(A(x)= \sum_{n=0}^{\infty} a_nx^n\) and \(B(x)=\sum_{n=0}^{\infty}a_nx^n\) be generating functions. Then \(A(x)B(x)\) is the generating function of the sequence whose \(n\)th term is given by
\(a_0b_n + a_1b_{n-1}+a_2b_{n-2}+ \cdot \cdot \cdot + a_nb_0 = \displaystyle \sum_{k=0}^n a_kb_{n-k}\).