Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 16.5 Power Series

Subsection 16.5.1 Definition

Earlier in this chapter, we found that a polynomial of degree \(n\) over a ring \(R\) is an expression of the form
\begin{equation*} f(x)=\sum_{i=0}^n a_i x^i=a_0 + a_1 x+a_2 x^2+ \cdots +a_n x^n \end{equation*}
where \(n\geq 0\text{,}\) each of the \(a_i\) are elements of \(R\) and \(a_n\neq 0\text{.}\) In Section 8.5 we defined a generating function of a sequence \(s\) with terms \(s_0\text{,}\) \(s_1\text{,}\) \(s_2, \ldots\) as the infinite sum
\begin{equation*} G(s,z)= \sum_{i=0}^{\infty } s_i z^i=s_0 + s_1 z+s_2 z^2+ \cdots \end{equation*}
The main difference between these two expressions, disregarding notation, is that the latter is an infinite expression and the former is a finite expression. In this section we will extend the algebra of polynomials to the algebra of infinite expressions like \(G(s, z)\text{,}\) which are called power series.

Definition 16.5.1. Power Series.

Let \([R; +,\cdot ]\) be a ring. A power series over \(R\) is an expression of the form
\begin{equation*} f(x)=\sum_{i=0}^{\infty } a_i x^i=a_0 + a_1 x+a_2 x^2+ \cdots \end{equation*}
where \(a_1, a_2, a_3,\ldots \in R\text{.}\) The set of all such expressions is denoted by \(R[[x]]\text{.}\)
Our first observation in our comparison of \(R[x]\) and \(R[[x]]\) is that every polynomial is a power series and so \(R[x]\subseteq R[[x]]\text{.}\) This is true because a polynomial \(a_0 + a_1 x+a_2 x^2+ \cdots +a_n x^n\) of degree \(n\) in \(R[x]\text{,}\) can be thought of as an infinite expression where \(a_i=0\) for \(i > n\text{.}\) In addition, we will see that \(R[[x]]\) is a ring with subring \(R[x]\text{.}\)
\(R[[x]]\) is given a ring structure by defining addition and multiplication on power series as we did in \(R[x]\text{,}\) with the modification that, since we are dealing with infinite expressions, the sums and products will remain infinite expressions that we can determine term by term, as was done in with polynomials.

Definition 16.5.2. Power Series Addition.

Given power series
\begin{equation*} \begin{array}{c} f(x)=\sum_{i=0}^{\infty } a_i x^i=a_0 + a_1 x+a_2 x^2+ \cdots\textrm{ and}\\ g(x)=\sum_{i=0}^{\infty } b_i x^i=b_0 + b_1 x+b_2 x^2+ \cdots\\ \end{array} \end{equation*}
their sum is
\begin{equation*} \begin{split} f(x)+g(x)&=\sum_{i=0}^{\infty }\left(a_i+b_i\right) x^i\\ &=(a_0 +b_0) + (a_1+b_1) x+(a_2+b_2) x^2+(a_3+b_3) x^3+ \cdots \\ \end{split}\text{.} \end{equation*}

Definition 16.5.3. Power Series Multiplication.

Given power series
\begin{equation*} \begin{array}{c} f(x)=\sum_{i=0}^{\infty } a_i x^i=a_0 + a_1 x+a_2 x^2+ \cdots\textrm{ and}\\ g(x)=\sum_{i=0}^{\infty } b_i x^i=b_0 + b_1 x+b_2 x^2+ \cdots\\ \end{array} \end{equation*}
their product is
\begin{equation*} \begin{split} f(x)\cdot g(x)&=\sum_{i=0}^{\infty } d_i x^i \quad \textrm{where }d_i= \sum_{j=0}^i a_j b_{i-j}\\ &=(a_0\cdot b_0) + (a_0\cdot b_1+a_1\cdot b_0) x+(a_0\cdot b_2+a_1\cdot b_1+a_2\cdot b_0) x^2+ \cdots \\ \end{split}\text{.} \end{equation*}

Example 16.5.4. Some Power Series Calcuations.

Let
\begin{equation*} \begin{array}{c} f(x)=\sum_{i=0}^{\infty} i x^i=0 + 1 x+2 x^2+3x^3+ \cdots \quad \textrm{and}\\ g(x)=\sum_{i=0}^{\infty} 2^i x^i=1 +2 x+4 x^2+8x^3+ \cdots \\ \end{array} \end{equation*}
be elements in \(\mathbb{Z}[[x]]\text{.}\) Let us compute \(f(x) + g(x)\) and \(f(x)\cdot g(x)\text{.}\) First the sum:
\begin{equation*} \begin{split} f(x) + g(x) & =\sum_{i=0}^{\infty } i x^i+\sum_{i=0}^{\infty } 2^i x^i\\ &=\sum_{i=0}^{\infty} \left(i+2^i\right) x^i\\ & =1+3x+6x^2+11x^3+ \cdots\\ \end{split} \end{equation*}
The product is a bit more involved:
\begin{equation*} \begin{split} f(x) \cdot g(x) & =\left(\sum_{i=0}^{\infty } i x^i\right)\cdot \left(\sum_{i=0}^{\infty } 2^i x^i\right)\\ &=\left(0+ 1 x+2 x^2+3x^3+ \cdots \right)\cdot \left(1 +2 x+4 x^2+8x^3+ \cdots \right)\\ &=0\cdot 1 + (0\cdot 2 + 1\cdot 1)x + (0\cdot 4+1\cdot 2+2\cdot 1)x^2+ \cdots\\ &= x + 4 x^2+ 11 x^3 + \cdots\\ &= \sum_{i=0}^{\infty } d_i x^i\quad\quad\textrm{where } d_i= \sum_{j=0}^i j 2^{i-j}\\ \end{split} \end{equation*}
We can compute any value of \(d_i\text{,}\) with the amount of time/work required increasing as \(i\) increases.
A closed-form expression for \(d_i\) would be desirable. Using techniques from Chapter 8, the formula is \(d_i=2^{i+1}-i-2\text{,}\) which we leave it to the reader to derive. Hence, \(f(x)\cdot g(x) =\sum_{i=0}^{\infty } (2^{i+1}-i-2) x^i\)

Subsection 16.5.2 Properties, Units

We have seen that addition and multiplication in \(R[[x]]\) is virtually identical to that in \(R[x]\text{.}\) The following theorem parallels Theorem 16.3.8, establishing the ring properties of \(R[[x]]\text{.}\)
We are most interested in the situation when the set of coefficients is a field. The theorem above indicates that when \(F\) is a field, \(F[[x]]\) is an integral domain. A reason that \(F[[x]]\) is not a field is the same as one that we can cite for \(F[x]\text{,}\) namely that \(x\) does not have multiplicative inverse in \(F[[x]]\text{.}\)
With all of these similarities, one might wonder if the rings of polynomials and power series over a field are isomorphic. It turns out that they are not. The difference between \(F[x]\) and \(F[[x]]\) becomes apparent when one studies which elements are units in each. First we prove that the only units in \(F[x]\) are the nonzero constants; that is, the nonzero elements of \(F\text{.}\)

Proof.

(⇒) 
Let \(f(x)\) be a unit in \(F[x]\text{.}\) Then \(f(x)\) has a multiplicative inverse, call it \(g(x)\text{,}\) such that \(f(x) \cdot g(x) = 1\text{.}\) Hence, the \(\deg (f(x)\cdot g(x)) = \deg (1) = 0\text{.}\) But \(\deg (f(x)\cdot g(x)) = \deg f(x) + \deg g(x)\text{.}\) So \(\deg f(x) + \deg g(x) = 0\text{,}\) and since the degree of a polynomial is always nonnegative, this can only happen when the \(\deg f(x) = \deg g(x) = 0\text{.}\) Hence, \(f(x)\) is a constant, an element of \(F\text{,}\) which is a unit if and only if it is nonzero.
(⇐) 
If \(f(x)\) is a nonzero element of \(F\text{,}\) then it is a unit since \(F\) is a field. Thus it has an inverse, which is also in \(F[x]\) and so \(f(x)\) is a unit of \(F[x]\text{.}\)
Before we proceed to categorize the units in \(F[[x]]\text{,}\) we remind the reader that two power series \(a_0 + a_1 x+a_2 x^2+ \cdots\) and \(b_0 + b_1 x+b_2 x^2+ \cdots\) are equal if and only if corresponding coefficients are equal, \(a_i=b_i\) for all \(i \geq 0\text{.}\)

Proof.

(⇒) 
If \(f(x)\) is a unit of \(F[[x]]\text{,}\) then there exists \(g(x)=\sum_{i=0}^{\infty } b_i x^i\) in \(F[[x]]\) such that
\begin{equation*} \begin{split} f(x)\cdot g(x) &=\left(a_0 + a_1 x+a_2 x^2+ \cdots \right)\cdot \left(b_0 + b_1 x+b_2 x^2+ \cdots \right)\\ & =1\\ & = 1 + 0x + 0x^2+ \cdots\\ \end{split}\text{.} \end{equation*}
Since corresponding coefficients in the equation above must be equal, \(a_0\cdot b_0=1\text{,}\) which implies that \(a_0\neq 0\text{.}\)
(⇐) 
Assume that \(a_0\neq 0\text{.}\) To prove that \(f(x)\) is a unit of \(F[[x]]\) we need to find \(g(x)=\sum_{i=0}^{\infty } b_i x^i\) in \(F[[x]]\) such that \(f(x) \cdot g(x) =\sum_{i=0}^{\infty } d_i x^i= 1\text{.}\) If we use the formula for the coefficients \(f(x) \cdot g(x)\) and equate coefficients, we get
\begin{equation*} \begin{array}{lll} d_0= a_0\cdot b_0= 1 &\Rightarrow & b_0=a_0{}^{-1} \\ d_1= a_0\cdot b_1+ a_1\cdot b_0=0&\Rightarrow & b_1= -a_0{}^{-1}\cdot \left(a_1\cdot b_0\right) \\ d_2=a_0 b_2+a_1 b_1+a_2 b_0=0 & \Rightarrow & b_2=-a_0{}^{-1}\cdot \left(a_1\cdot b_1+ a_2\cdot b_0\right)\\ \vdots & \vdots & \vdots \\ d_s= a_0\cdot b_s+ a_1\cdot b_{s-1}+ \cdots +a_s\cdot b_0 =0 & \Rightarrow &b_s= -a_0{}^{-1}\cdot \left(a_1\cdot b_{s-1}+ a_2\cdot b_{s-2}+ \cdots +a_s\cdot b_0\right)\\ \end{array}\text{.} \end{equation*}
Therefore the powers series \(\sum_{i=0}^{\infty } b_i x^i\) is an expression whose coefficients lie in \(F\) and that satisfies the statement \(f(x) \cdot g(x) = 1\text{.}\) Hence, \(g(x)\) is the multiplicative inverse of \(f(x)\) and \(f(x)\) is a unit.

Example 16.5.8.

Let \(f(x) =1 + 2x + 3 x^2+ 4 x^3+ \cdots =\sum_{i=0}^{\infty } (i+1) x^i\) be an element of \(\mathbb{Q}[[x]]\text{.}\) Then, by Theorem 16.5.7, since \(a_0=1\neq 0\text{,}\) \(f(x)\) is a unit and has an inverse, call it \(g(x)\text{.}\) To compute \(g(x)\text{,}\) we follow the procedure outlined in the above theorem. Using the formulas for the \(b_i'\)s, we obtain
\begin{equation*} \begin{array}{c} b_0 = 1\\ b_1= -1(2\cdot 1)=-2\\ b_2= -1(2\cdot (-2)+ 3\cdot 1) = 1\\ b_3= -1(2\cdot 1 + 3\cdot (-2)+4\cdot 1)=0\\ b_4= -1(2\cdot 0+3\cdot 1 + 4\cdot (-2)+5\cdot 1)=0\\ b_5= -1(2\cdot 0+3\cdot 0+4\cdot (1)+5\cdot (-2)+6\cdot 1)=0\\ \vdots \\ \end{array} \end{equation*}
For \(s \geq 3\text{,}\) we have
\begin{equation*} b_s= -1(2\cdot 0 + 3\cdot 0+\cdots (s-2)\cdot 0+(s-1)\cdot 1+s\cdot (-2)+(s+1)\cdot 1)=0 \end{equation*}
Hence, \(g(x) = 1 - 2x +x^2\) is the multiplicative inverse of \(f(x)\text{.}\)
Certainly \(F[[x]]\) contains a wider variety of units than \(F[x]\text{.}\) Yet \(F[[x]]\) is not a field, since \(x\in F[[x]]\) is not a unit. So concerning the algebraic structure of \(F[[x]]\text{,}\) we know that it is an integral domain that contains \(F[x]\text{.}\) If we allow our power series to take on negative exponents; that is, consider expressions of the form \(f(x) =\sum_{i=-\infty }^{\infty } a_i x^i\) where all but a finite number of terms with a negative index equal zero. These expressions are called extended power series. The set of all such expressions is a field, call it \(E\text{.}\) This set does contain, for example, the inverse of \(x\text{,}\) which is \(x^{-1}\text{.}\) It can be shown that each nonzero element of \(E\) is a unit.

Exercises 16.5.3 Exercises

1.

Let \(f(x)=\sum_{i=0}^{\infty} a_i x^i\) and \(g(x)=\sum_{i=0}^{\infty } b_i x^i\) be elements of \(R[[x]]\text{.}\) Let \(f(x) \cdot g(x) =\sum_{i=0}^{\infty } d_i x^i= 1\text{.}\) Apply basic algebra to \(\left(a_0 + a_1 x+a_2 x^2+ \cdots \right)\cdot \left(b_0 + b_1 x+b_2 x^2+ \cdots \right)\) to derive the formula \(d_s= \sum_{i=0}^s a_i b_{s-i}\) for the coefficients of \(f(x) \cdot g(x)\text{.}\) Hence, to show that \(f(x) \cdot g(x) =\sum_{s=0}^{\infty } \left(\sum_{i=0}^s a_i b_{s-i}\right) x^s\)

2.

  1. Prove that for any integral domain \(D\text{,}\) the following can be proven: \(f(x)=\sum_{i=0}^{\infty } a_i x^i\) is a unit of \(D[[x]]\) if and only if \(a_0\) is a unit in \(D\text{.}\)
  2. Compare the statement in part a to that in Theorem 16.5.7.
  3. Give an example of the statement in part a in \(\mathbb{Z}[[x]]\text{.}\)

3.

Use the formula for the product to verify that the expression \(g(x)\) of Example 16.5.8 is indeed the inverse of \(f(x)\text{.}\)

4.

  1. Determine the inverse of \(f(x) = 1 + x + x^2 + \cdots = \sum_{i=0}^{\infty } x^i\)in \(\mathbb{Q}[[x]]\text{.}\)
  2. Repeat part a with \(f(x)\) taken in \(\mathbb{Z}_2[[x]]\text{.}\)
  3. Use the method outlined in Chapter 8 to show that the power series \(f(x) = \sum_{i=0}^{\infty } x^i\) is the rational generating function \(\frac{1}{1-x}\text{.}\) What is the inverse of this function? Compare your results with those in part a.

5.

  1. Determine the inverse of \(h(x) = \sum_{i=0}^{\infty } 2^i x^i\) in \(\mathbb{Q}[[x]]\text{.}\)
  2. Use the procedures in Chapter 8 to find a rational generating function for \(h(x)\) in part a. Find the multiplicative inverse of this function.
Answer.
  1. \begin{equation*} \begin{array}{c} b_0= 1\\ b_1=(-1)(2\cdot 1) = -2\\ b_2=(-1)(2\cdot (-2)+4\cdot 1)= 0\\ b_3= (-1)(2\cdot 0 + 4\cdot (-2)+8\cdot 1)=0\\ \end{array} \end{equation*}
    All other terms are zero. Hence, \(f(x)^{-1}= 1-2x\)
  2. \begin{equation*} \begin{split} f(x) &=1+2x + 2^2x^2+ 2^3x^3+ \cdots \\ &=(2x)^0 + (2x)^1 + (2x)^2+ (2x)^3+\cdots \\ &= \frac{1}{1-2x}\\ \end{split} \end{equation*}
    The last step follows from the formula for the sum of a geometric series.

6.

Let \(a(x) = 1 + 3x + 9x^2 + 27x^3 + \cdots =\sum_{i=0}^{\infty } 3^i x^i\) and \(b(x) = 1 + x + x^2+ x^3+\cdots =\sum_{i=0}^{\infty } x^i\) both in \(\mathbb{R}[[x]]\text{.}\)
  1. What are the first four terms (counting the constant term as the \(0^{\textrm{ th}}\) term) of \(a(x) + b(x)\text{?}\)
  2. Find a closed form expression for \(a(x)\text{.}\)
  3. What are the first four terms of \(a(x) b(x)\text{?}\)

7.

Write as an extended power series:
  1. \(\displaystyle \left(x^4-x^5\right)^{-1}\)
  2. \(\displaystyle \left(x^2-2x^3+x^4\right)^{-1}\)
Answer.
  1. \begin{equation*} \begin{split} \left(x^4-x^5\right)^{-1} & =(x^4 (1-x))^{-1}\\ &=x^{-4}\frac{1}{1-x}\\ & =x^{-4}\left(\sum_{k=0}^{\infty } x^k\right)\\ &=\sum_{k=-4}^{\infty} x^k\\ \end{split}\text{.} \end{equation*}
  2. \begin{equation*} \begin{split} \left(x^4-2 x^3+x^2\right)^{-1} & =\left(x^2 \left(x^2-2 x+1\right)\right)^{-1}\\ &=x^{-2}\left(1-2x+x^2\right)^{-1}\\ & =x^{-2}\left(\sum_{k=0}^{\infty } (k+1) x^k\right)\\ &=\sum_{k=-2}^{\infty} (k+2) x^k\\ \end{split}\text{.} \end{equation*}

8.

Derive the closed form expression \(d_i = 2^{i+1}-i -2 \) for the coefficients of the product \(f(x)\cdot g(x)\) in Example 16.5.4.
You have attempted of activities on this page.
PrevTopNext