Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 3] FUNCTIONS AND ALGORITHMS 51

Sequences

Asequenceis a function from the setN={ 1 , 2 , 3 ,...}of positive integers into a setA. The notationanis
used to denote the image of the integern. Thus a sequence is usually denoted by

a 1 ,a 2 ,a 3 ,... or {an:n∈N} or simply {an}

Sometimes the domain of a sequence is the set{ 0 , 1 , 2 ,...}of nonnegative integers rather thanN. In such a ease
we saynbegins with 0 rather than 1.

Afinite sequenceover a setAis a function from{ 1 , 2 ,...,m}intoA, and it is usually denoted by

a 1 ,a 2 ,...,am

Such a finite sequence is sometimes called alistor anm-tuple.

EXAMPLE 3.5

(a) The following are two familiar sequences:

(i) 1,^12 ,^13 ,^14 ,...which may be defined byan=^1 n;

(ii) 1,^12 ,^14 ,^18 ,...which may be defined bybn= 2 −n

Note that the first sequence begins withn=1 and the second sequence begins withn=0.

(b) The important sequence 1,− 1 , 1 ,− 1 ,...may be formally defined by

an=(− 1 )n+^1 or,equivalently,by bn=(− 1 )n

where the first sequence begins withn=1 and the second sequence begins withn=0.

(c) Strings Suppose a setAis finite andAis viewed as a character set or an alphabet. Then a finite sequence

overAis called astringorword, and it is usually written in the forma 1 a 2 ...am, that is, without parentheses.

The numbermof characters in the string is called itslength. One also views the set with zero characters as a

string; it is called theempty stringornull string. Strings over an alphabetAand certain operations on these

strings will be discussed in detail in Chapter 13.

Summation Symbol, Sums

Here we introduce the summation symbol

∑
(the Greek letter sigma). Consider a sequencea 1 ,a 2 ,a 3 ,....
Then we define the following:

∑n

J= 1

aj=a 1 +a 2 +···+an and

∑n

j=m

aj=am+am+ 1 +···+an

The letterjin the above expressions is called adummy indexordummy variable. Other letters frequently used as
dummy variables arei,k,s, andt.

EXAMPLE 3.6 n
∑
i= 1

aibi=a 1 b 1 +a 2 b 2 +···+anbn

∑^5

j= 2

j^2 = 22 + 32 + 42 + 52 = 4 + 9 + 16 + 25 = 54

∑n

j= 1

j= 1 + 2 +···+n