Page 178 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 157

DEFINITION 2 A geometric progression is a sequence of the form

n
2
a, ar, ar ,...,ar ,...
where the initial term a and the common ratio r are real numbers.

Remark: A geometric progression is a discrete analogue of the exponential function f(x) =
x
ar .
n
n
n
EXAMPLE 2 The sequences {b n } with b n = (−1) , {c n } with c n = 2 · 5 , and {d n } with d n = 6 · (1/3) are
geometric progressions with initial term and common ratio equal to 1 and −1; 2 and 5; and 6
and 1/3, respectively, if we start at n = 0. The list of terms b 0 ,b 1 ,b 2 ,b 3 ,b 4 ,... begins with
1, −1, 1, −1, 1,... ;
the list of terms c 0 ,c 1 ,c 2 ,c 3 ,c 4 ,... begins with

2, 10, 50, 250, 1250,... ;
and the list of terms d 0 ,d 1 ,d 2 ,d 3 ,d 4 ,... begins with
2 2 2 ▲
6, 2, , , ,....
3 9 27

DEFINITION 3 An arithmetic progression is a sequence of the form

a, a + d, a + 2d,...,a + nd,...

where the initial term a and the common difference d are real numbers.

Remark: An arithmetic progression is a discrete analogue of the linear function f(x) = dx + a.

EXAMPLE 3 The sequences {s n } with s n =−1 + 4n and {t n } with t n = 7 − 3n are both arithmetic progres-
sions with initial terms and common differences equal to −1 and 4, and 7 and −3, respectively,
if we start at n = 0. The list of terms s 0 ,s 1 ,s 2 ,s 3 ,... begins with
−1, 3, 7, 11,...,

and the list of terms t 0 ,t 1 ,t 2 ,t 3 ,... begins with
▲
7, 4, 1, −2,....
Sequences of the form a 1 ,a 2 ,...,a n are often used in computer science. These finite
sequences are also called strings. This string is also denoted by a 1 a 2 ...a n . (Recall that bit
strings, which are finite sequences of bits, were introduced in Section 1.1.) The length of a
string is the number of terms in this string. The empty string, denoted by λ, is the string that
has no terms. The empty string has length zero.
EXAMPLE 4 The string abcd is a string of length four. ▲

Recurrence Relations

In Examples 1–3 we specified sequences by providing explicit formulas for their terms. There
are many other ways to specify a sequence. For example, another way to specify a sequence is