Page 177 - Discrete Mathematics and Its Applications

156 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

2.4 Sequences and Summations

Introduction

Sequences are ordered lists of elements, used in discrete mathematics in many ways. For ex-
ample, they can be used to represent solutions to certain counting problems, as we will see in
Chapter 8. They are also an important data structure in computer science. We will often need
to work with sums of terms of sequences in our study of discrete mathematics. This section
reviews the use of summation notation, basic properties of summations, and formulas for the
sums of terms of some particular types of sequences.
The terms of a sequence can be specified by providing a formula for each term of the
sequence. In this section we describe another way to specify the terms of a sequence using
a recurrence relation, which expresses each term as a combination of the previous terms. We
will introduce one method, known as iteration, for finding a closed formula for the terms of a
sequence specified via a recurrence relation. Identifying a sequence when the first few terms
are provided is a useful skill when solving problems in discrete mathematics. We will provide
some tips, including a useful tool on the Web, for doing so.

Sequences

A sequence is a discrete structure used to represent an ordered list. For example, 1, 2, 3, 5, 8 is
n
a sequence with five terms and 1, 3, 9, 27, 81 ,... ,3 , ... is an infinite sequence.

DEFINITION 1 A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2,...}
or the set {1, 2, 3,...})toaset S. We use the notation a n to denote the image of the integer n.
We call a n a term of the sequence.

We use the notation {a n } to describe the sequence. (Note that a n represents an individual
term of the sequence {a n }. Be aware that the notation {a n } for a sequence conflicts with the
notation for a set. However, the context in which we use this notation will always make it clear
when we are dealing with sets and when we are dealing with sequences. Moreover, although we
have used the letter a in the notation for a sequence, other letters or expressions may be used
depending on the sequence under consideration. That is, the choice of the letter a is arbitrary.)
We describe sequences by listing the terms of the sequence in order of increasing subscripts.

EXAMPLE 1 Consider the sequence {a n }, where

1
a n = .
n

The list of the terms of this sequence, beginning with a 1 , namely,

a 1 ,a 2 ,a 3 ,a 4 ,...,

starts with

1 1 1
1, , , ,.... ▲
2 3 4