Page 182 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 161

When trying to deduce a possible formula, recurrence relation, or some other type of rule
for the terms of a sequence when given the initial terms, try to find a pattern in these terms.You
might also see whether you can determine how a term might have been produced from those
preceding it. There are many questions you could ask, but some of the more useful are:
Are there runs of the same value? That is, does the same value occur many times in a
row?
Are terms obtained from previous terms by adding the same amount or an amount that
depends on the position in the sequence?
Are terms obtained from previous terms by multiplying by a particular amount?
Are terms obtained by combining previous terms in a certain way?
Are there cycles among the terms?

EXAMPLE 12 Find formulae for the sequences with the following first five terms: (a) 1, 1/2, 1/4, 1/8, 1/16
(b) 1, 3, 5, 7, 9 (c) 1, −1, 1, −1, 1.

n
Solution: (a) We recognize that the denominators are powers of 2.The sequence with a n = 1/2 ,
n = 0, 1, 2, ... is a possible match. This proposed sequence is a geometric progression with
a = 1 and r = 1/2.
(b) We note that each term is obtained by adding 2 to the previous term. The sequence
with a n = 2n + 1,n = 0, 1, 2,... is a possible match. This proposed sequence is an arithmetic
progression with a = 1 and d = 2.
n
(c) The terms alternate between 1 and −1. The sequence with a n = (−1) , n = 0, 1, 2 ...
is a possible match. This proposed sequence is a geometric progression with a = 1 and r =−1.
▲

Examples 13–15 illustrate how we can analyze sequences to find how the terms are con-
structed.

EXAMPLE 13 How can we produce the terms of a sequence if the first 10 terms are 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

Solution: In this sequence, the integer 1 appears once, the integer 2 appears twice, the integer 3
appears three times, and the integer 4 appears four times. A reasonable rule for generating this
sequence is that the integer n appears exactly n times, so the next five terms of the sequence
would all be 5, the following six terms would all be 6, and so on. The sequence generated this
way is a possible match. ▲

EXAMPLE 14 How can we produce the terms of a sequence if the first 10 terms are 5, 11, 17, 23, 29, 35, 41,
47, 53, 59?

Solution: Note that each of the first 10 terms of this sequence after the first is obtained by adding
6 to the previous term. (We could see this by noticing that the difference between consecutive
terms is 6.) Consequently, the nth term could be produced by starting with 5 and adding 6 a
total of n − 1 times; that is, a reasonable guess is that the nth term is 5 + 6(n − 1) = 6n − 1.
(This is an arithmetic progression with a = 5 and d = 6.) ▲

EXAMPLE 15 How can we produce the terms of a sequence if the first 10 terms are 1, 3, 4, 7, 11, 18, 29, 47,
76, 123?

Solution: Observe that each successive term of this sequence, starting with the third term,
is the sum of the two previous terms. That is, 4 = 3 + 1, 7 = 4 + 3, 11 = 7 + 4, and so on.
Consequently, if L n is the nth term of this sequence, we guess that the sequence is determined
by the recurrence relation L n = L n−1 + L n−2 with initial conditions L 1 = 1 and L 2 = 3 (the