Mathematics for Computer Science

(avery) #1

15.5. Formal Power Series 645


These operations on infinite sequences have lots of nice properties. For example,
it’s easy to check that sequence addition and multiplication are commutative:


G ̊HDH ̊G;
G ̋HDH ̋G:

If we let


ZWWD.0;0;0;:::/;
IWWD.1;0;0;:::;0;:::/;

then it’s equally easy to check thatZacts like a zero for sequences andIacts like
the number one:


Z ̊GDG;
Z ̋GDZ; (15.20)
I ̋GDG:

Now if we define
GWWD.g 0 ;g 1 ;g 2 ;:::/


then
G ̊.G/DZ:


In fact, the operations ̊and ̋satisfy all thecommutative ringaxioms described
in Section 8.7.1. The set of infinite sequences of numbers together with these op-
erations is called thering of formal power seriesover these numbers.^5
A sequenceHis thereciprocalof a sequenceGwhen


G ̋HDI:

A reciprocal ofGis also called amultiplicative inverseor simply an “inverse”
ofG. The ring axioms imply that if there is a reciprocal, it is unique (see Prob-
lem 8.32), so the suggestive notation1=Gcan be used unambiguously to denote
this reciprocal, if it exists. For example, letting


JWWD.1;1;0;0;:::;0;:::/
KWWD.1;1;1;1;:::;1;:::/;

the definition of ̋implies thatJ ̋KDI, and soKD1=JandJD1=Ke.


(^5) The elements in the sequences may be the real numbers, complex numbers, or, more generally,
may be the elements from any given commutative ring.

Free download pdf