Page 189 - Discrete Mathematics and Its Applications

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

n
n
f) the sequence whose nth term is the largest integer c) a n = 3(−1) + 2 − n + 2.
n
whose binary expansion (defined in Section 4.2) has d) a n = 7 · 2 − n + 2.
n bits (Write your answer in decimal notation.) 16. Findthesolutiontoeachoftheserecurrencerelationswith
g) the sequence whose terms are constructed sequen- thegiveninitialconditions.Useaniterativeapproachsuch
tially as follows: start with 1, then add 1, then multiply as that used in Example 10.
by 1, then add 2, then multiply by 2, and so on a) a n =−a n−1 ,a 0 = 5
h) the sequence whose nth term is the largest integer k b) a n = a n−1 + 3,a 0 = 1
such that k!≤ n
c) a n = a n−1 − n, a 0 = 4
7. Find at least three different sequences beginning with the
d) a n = 2a n−1 − 3,a 0 =−1
terms 1, 2, 4 whose terms are generated by a simple for-
e) a n = (n + 1)a n−1 ,a 0 = 2
mula or rule.
f) a n = 2na n−1 ,a 0 = 3
8. Find at least three different sequences beginning with the g) a n =−a n−1 + n − 1,a 0 = 7
terms 3, 5, 7 whose terms are generated by a simple for-
17. Find the solution to each of these recurrence relations and
mula or rule.
initial conditions. Use an iterative approach such as that
9. Find the first five terms of the sequence defined by each used in Example 10.
of these recurrence relations and initial conditions.
a) a n = 3a n−1 , a 0 = 2
a) a n = 6a n−1 , a 0 = 2 b) a n = a n−1 + 2, a 0 = 3
b) a n = a 2 , a 1 = 2
n−1 c) a n = a n−1 + n, a 0 = 1
c) a n = a n−1 + 3a n−2 , a 0 = 1, a 1 = 2 d) a n = a n−1 + 2n + 3, a 0 = 4
2
d) a n = na n−1 + n a n−2 , a 0 = 1, a 1 = 1
e) a n = 2a n−1 − 1, a 0 = 1
e) a n = a n−1 + a n−3 , a 0 = 1, a 1 = 2, a 2 = 0
f) a n = 3a n−1 + 1, a 0 = 1
10. Find the first six terms of the sequence defined by each g) a n = na n−1 , a 0 = 5
of these recurrence relations and initial conditions. h) a n = 2na n−1 , a 0 = 1
a) a n =−2a n−1 , a 0 =−1 18. A person deposits $1000 in an account that yields 9%
b) a n = a n−1 − a n−2 , a 0 = 2, a 1 =−1 interest compounded annually.
c) a n = 3a 2 ,a 0 = 1
n−1 a) Set up a recurrence relation for the amount in the ac-
d) a n = na n−1 + a 2 ,a 0 =−1,a 1 = 0
n−2 count at the end of n years.
e) a n = a n−1 − a n−2 + a n−3 ,a 0 = 1,a 1 = 1,a 2 = 2 b) Find an explicit formula for the amount in the account
n
n
11. Let a n = 2 + 5 · 3 for n = 0, 1, 2,.... at the end of n years.
a) Find a 0 ,a 1 ,a 2 ,a 3 , and a 4 . c) How much money will the account contain after 100
b) Show that a 2 = 5a 1 − 6a 0 ,a 3 = 5a 2 − 6a 1 , and years?
a 4 = 5a 3 − 6a 2 . 19. Suppose that the number of bacteria in a colony triples
c) Show that a n = 5a n−1 − 6a n−2 for all integers n with every hour.
n ≥ 2. a) Set up a recurrence relation for the number of bacteria
12. Show that the sequence {a n } is a solution of the recurrence after n hours have elapsed.
relation a n =−3a n−1 + 4a n−2 if b) If 100 bacteria are used to begin a new colony, how
a) a n = 0. b) a n = 1. many bacteria will be in the colony in 10 hours?
n
n
c) a n = (−4) . d) a n = 2(−4) + 3. 20. Assume that the population of the world in 2010 was 6.9
13. Is the sequence {a n } a solution of the recurrence relation billion and is growing at the rate of 1.1% a year.
a n = 8a n−1 − 16a n−2 if a) Set up a recurrence relation for the population of the
a) a n = 0? b) a n = 1? world n years after 2010.
n
n
c) a n = 2 ? d) a n = 4 ? b) Find an explicit formula for the population of the
n
n
n
e) a n = n4 ? f) a n = 2 · 4 + 3n4 ? world n years after 2010.
2 n
n
g) a n = (−4) ? h) a n = n 4 ? c) What will the population of the world be in 2030?
14. For each of these sequences find a recurrence relation 21. A factory makes custom sports cars at an increasing rate.
satisfied by this sequence. (The answers are not unique In the first month only one car is made, in the second
because there are infinitely many different recurrence month two cars are made, and so on, with n cars made in
relations satisfied by any sequence.) the nth month.
a) a n = 3 b) a n = 2n a) Set up a recurrence relation for the number of cars
c) a n = 2n + 3 d) a n = 5 n produced in the first n months by this factory.
2
e) a n = n 2 f) a n = n + n b) How many cars are produced in the first year?
g) a n = n + (−1) n h) a n = n! c) Find an explicit formula for the number of cars pro-
15. Show that the sequence {a n } is a solution of the recurrence duced in the first n months by this factory.
relation a n = a n−1 + 2a n−2 + 2n − 9if 22. An employee joined a company in 2009 with a starting
a) a n =−n + 2. salary of $50,000. Every year this employee receives a
n
b) a n = 5(−1) − n + 2. raise of $1000 plus 5% of the salary of the previous year.