Sequences and Subsequences 249Definition 3. An infinite sequence of elements of a set X is a function F : N --+ X.
A function F : {0, 1, 2, ... ., n - 11 -+ X for some n E N is a finite sequence of elements
of X of length n. The expression sequence of elements of X means a finite sequence of
elements of X or an infinite sequence of elements of X.
In computer programming, finite sequences are often called lists. Infinite sequencesare often called streams and sometimes also lists. Often, if F is a finite sequence of ele-
ments, then its elements are denoted not as
F(0), F(1),..., F(n - 1)
but, rather, as X X -.
Similarly, an infinite sequence is usually written as
Xo, X1, • -Xn,.An infinite sequence of real numbers is a function from N to R. For example,
0 1 2 n
Xo -, X1 -, X2=- ..... xn-.is an infinite sequence of real numbers.
For any X C R•, a sequence F of elements of X is increasing if, thought of as a
function from N to X, F is increasing. Thus, the sequence
0 1 2 nXO , Xl-, 1 X2 = ...... Xn-
is increasing. The terms increasing, decreasing, strictly increasing, and strictly decreas-
ing apply to sequences in the same way.
Example 6.
(a) The elements of a sequence need not be different. For example, 0, 0, 0, 0 .... is a se-
quence. Formally, this sequence is given by the function Zero : N -- N defined by the
rule Zero(n) = 0.
(b) Let F : N --+ Z be defined by the rule F(n) = (-1)n. Then, F is the sequence
1, -1, 1, -1, 1, -1 ....(c) Let Fact(n) = n!. Then, Fact defines the sequence
1,1,2,6,24, 120, 720....
An important notion associated with sequences is the notion of a subsequence. Intu-
itively, a subsequence is just a subset of a sequence, with the elements of the subsequence
occurring in the same order as they do in the sequence.
Example 7. For the sequence of factorials
1, 1, 2, 6, 24, 120, 720, 5040, 40,320, ...the following are subsequences:
(a) 0; the subsequence of length 0
(b) 1, 6, 120, 5040, ... ; every other factorial, starting with the second one
(c) 1, 1, 2, 6, 24, 120, 720, 5040, 40,320 .... ; the entire sequence
(d) I the first element alone
(e) 2, 6, 40,320; another finite subsequence