Discrete Mathematics for Computer Science

250 CHAPTER 4 Functions

What, more precisely, is a subsequence? Think of an infinite sequence:

XO, XI, X2, X3, X4, X5, X6 .....

Pick out a subset of the subscripts, such as subscripts

1,2,4,8, 16,32....

and then list the corresponding elements of the sequence in the same order as used in the

original sequence:

X1, X2, X4, X8, X16, X32,...

The chosen subscripts themselves form a sequence:

i0 = 1, il = 2, i 2 = 4, i 3 = 8, i 4 = 16, i 5 = 32....

So, the subsequence is

XiO, xiI , xi 2 , xi 3 , xi 4 , xi 5 , ....

(See Exercise 13 in Section 4.5 for missing details.) The important point is that the elements

are listed in the same order as in the original sequence; that is,

i0 < il < i2 < i3 <i4 < i5 < ...

is itself a strictly increasing sequence.

Definition 9. Let F be a sequence, and let S be a strictly increasing sequence of elements

of the domain of F. Then, F o S is a subsequence of F.

The proof that Definition 8 formalizes the previous discussion is left as an exercise.

Example 8. In the definition of a subsequence, the sequence S was required to be strictly

increasing. The sequence of elements in a sequence F are not required to be increasing; as

a result, the subsequence of elements determined by F o S need not be strictly increasing.

For example, let F : N -* IR where F(n) = (-1)n/(n + 1). So, F is the sequence

11 1

1, 1, - 2 -.- 3' 4 .....

(a) If S is the sequence 0, 2, 4 .... of even natural numbers, then F o S is the subsequence

consisting of every other element of the sequence F, starting with the first element:

1, -^1 -^1

3' 5'..

which is decreasing.

(b) If S is the sequence 1, 3, 5, ... of odd natural numbers, then F o S is the sequence

consisting of every other element of the sequence F, starting with the second element:

111

2' 4' 6''..

which is increasing.