Page 181 - Discrete Mathematics and Its Applications

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

At each iteration of the recurrence relation, we obtain the next term in the sequence by
adding 3 to the previous term. We obtain the nth term after n − 1 iterations of the recurrence
relation. Hence, we have added 3(n − 1) to the initial term a 0 = 2 to obtain a n . This gives us
the closed formula a n = 2 + 3(n − 1). Note that this sequence is an arithmetic progression. ▲

The technique used in Example 10 is called iteration. We have iterated, or repeatedly used,
the recurrence relation. The first approach is called forward substitution – we found successive
terms beginning with the initial condition and ending with a n . The second approach is called
backward substitution, because we began with a n and iterated to express it in terms of falling
terms of the sequence until we found it in terms of a 1 . Note that when we use iteration, we
essential guess a formula for the terms of the sequence. To prove that our guess is correct, we
need to use mathematical induction, a technique we discuss in Chapter 5.
In Chapter 8 we will show that recurrence relations can be used to model a wide variety of
problems. We provide one such example here, showing how to use a recurrence relation to find
compound interest.

EXAMPLE 11 Compound Interest Suppose that a person deposits $10,000 in a savings account at a bank
yielding 11% per year with interest compounded annually. How much will be in the account
after 30 years?

Solution: To solve this problem, let P n denote the amount in the account after n years. Because
the amount in the account after n years equals the amount in the account after n − 1 years plus
interest for the nth year, we see that the sequence {P n } satisfies the recurrence relation

P n = P n−1 + 0.11P n−1 = (1.11)P n−1 .

The initial condition is P 0 = 10,000.
We can use an iterative approach to find a formula for P n . Note that

P 1 = (1.11)P 0
2
P 2 = (1.11)P 1 = (1.11) P 0
3
P 3 = (1.11)P 2 = (1.11) P 0
.
.
.
n
P n = (1.11)P n−1 = (1.11) P 0 .
n
When we insert the initial condition P 0 = 10,000, the formula P n = (1.11) 10,000 is obtained.
n
Inserting n = 30 into the formula P n = (1.11) 10,000 shows that after 30 years the account
contains
30
P 30 = (1.11) 10,000 = $228,922.97. ▲

Special Integer Sequences

A common problem in discrete mathematics is finding a closed formula, a recurrence relation,
or some other type of general rule for constructing the terms of a sequence. Sometimes only a
few terms of a sequence solving a problem are known; the goal is to identify the sequence. Even
though the initial terms of a sequence do not determine the entire sequence (after all, there are
infinitely many different sequences that start with any finite set of initial terms), knowing the
first few terms may help you make an educated conjecture about the identity of your sequence.
Once you have made this conjecture, you can try to verify that you have the correct sequence.