Page 183 - Discrete Mathematics and Its Applications

162 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

TABLE 1 Some Useful Sequences.
nth Term First 10 Terms
n 2 1, 4, 9, 16, 25, 36, 49, 64, 81, 100,...
n 3 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000,...
n 4 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000,...
2 n 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,...
3 n 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,...
n! 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,...
f n 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

same recurrence relation as the Fibonacci sequence, but with different initial conditions). This
sequence is known as the Lucas sequence, after the French mathematician François Édouard
Lucas. Lucas studied this sequence and the Fibonacci sequence in the nineteenth century. ▲

Another useful technique for finding a rule for generating the terms of a sequence is to
compare the terms of a sequence of interest with the terms of a well-known integer sequence,
such as terms of an arithmetic progression, terms of a geometric progression, perfect squares,
perfect cubes, and so on. The first 10 terms of some sequences you may want to keep in mind
are displayed in Table 1.
EXAMPLE 16 Conjecture a simple formula for a n if the first 10 terms of the sequence {a n } are 1, 7, 25, 79,
241, 727, 2185, 6559, 19681, 59047.
Solution: To attack this problem, we begin by looking at the difference of consecutive terms,
but we do not see a pattern. When we form the ratio of consecutive terms to see whether each
term is a multiple of the previous term, we find that this ratio, although not a constant, is close
to 3. So it is reasonable to suspect that the terms of this sequence are generated by a formula
n
n
involving 3 . Comparing these terms with the corresponding terms of the sequence {3 },we
n
notice that the nth term is 2 less than the corresponding power of 3. We see that a n = 3 − 2
for 1 ≤ n ≤ 10 and conjecture that this formula holds for all n. ▲
We will see throughout this text that integer sequences appear in a wide range of contexts in
discrete mathematics. Sequences we have encountered or will encounter include the sequence
of prime numbers (Chapter 4), the number of ways to order n discrete objects (Chapter 6), the
number of moves required to solve the famous Tower of Hanoi puzzle with n disks (Chapter 8),
and the number of rabbits on an island after n months (Chapter 8).
Check out the puzzles at
Integer sequences appear in an amazingly wide range of subject areas besides discrete
the OEIS site.
mathematics, including biology, engineering, chemistry, and physics, as well as in puzzles. An
amazing database of over 200,000 different integer sequences can be found in the On-Line
Encyclopedia of Integer Sequences (OEIS). This database was originated by Neil Sloane in the
1960s. The last printed version of this database was published in 1995 ([SIPI95]); the current
encyclopedia would occupy more than 750 volumes of the size of the 1995 book with more than
10,000 new submissions a year. There is also a program accessible via the Web that you can use
to find sequences from the encyclopedia that match initial terms you provide.

Summations

Next, we consider the addition of the terms of a sequence. For this we introduce summation
notation. We begin by describing the notation used to express the sum of the terms

a m ,a m+1 ,...,a n