Page 545 - Discrete Mathematics and Its Applications

524 8 / Advanced Counting Techniques

Note that a n satisfies the linear nonhomogeneous recurrence relation

a n = a n−1 + n.

(To obtain a n , the sum of the first n positive integers, from a n−1 , the sum of the first n − 1
positive integers, we add n.) Note that the initial condition is a 1 = 1.
The associated linear homogeneous recurrence relation for a n is

a n = a n−1 .

(h) n
The solutions of this homogeneous recurrence relation are given by a n = c(1) = c,
where c is a constant. To find all solutions of a n = a n−1 + n, we need find only a single partic-
n
ular solution. By Theorem 6, because F(n) = n = n · (1) and s = 1 is a root of degree one of
the characteristic equation of the associated linear homogeneous recurrence relation, there is a
2
particular solution of the form n(p 1 n + p 0 ) = p 1 n + p 0 n.
2
2
Inserting this into the recurrence relation gives p 1 n + p 0 n = p 1 (n − 1) +
p 0 (n − 1) + n. Simplifying, we see that n(2p 1 − 1) + (p 0 − p 1 ) = 0, which means
that 2p 1 − 1 = 0 and p 0 − p 1 = 0, so p 0 = p 1 = 1/2. Hence,
n 2 n n(n + 1)
(p)
a n = + =
2 2 2
is a particular solution. Hence, all solutions of the original recurrence relation a n = a n−1 + n are
(h) (p)
given by a n = a n + a n = c + n(n + 1)/2. Becausea 1 = 1, we have 1 = a 1 = c + 1 · 2/2 =
c + 1, so c = 0. It follows that a n = n(n + 1)/2. (This is the same formula given in Table 2 in
Section 2.4 and derived previously.) ▲
Exercises

1. Determine which of these are linear homogeneous recur- 4. Solve these recurrence relations together with the initial
rence relations with constant coefficients. Also, find the conditions given.
degree of those that are. a) a n = a n−1 + 6a n−2 for n ≥ 2, a 0 = 3, a 1 = 6
a) a n = 3a n−1 + 4a n−2 + 5a n−3 b) a n = 7a n−1 − 10a n−2 for n ≥ 2, a 0 = 2, a 1 = 1
c) a n = 6a n−1 − 8a n−2 for n ≥ 2, a 0 = 4, a 1 = 10
b) a n = 2na n−1 + a n−2 c) a n = a n−1 + a n−4
d) a n = a n−1 + 2 e) a n = a 2 + a n−2 d) a n = 2a n−1 − a n−2 for n ≥ 2, a 0 = 4, a 1 = 1
n−1
f) a n = a n−2 g) a n = a n−1 + n e) a n = a n−2 for n ≥ 2, a 0 = 5, a 1 =−1
2. Determine which of these are linear homogeneous recur- f) a n =−6a n−1 − 9a n−2 for n ≥ 2, a 0 = 3, a 1 =−3
rence relations with constant coefficients. Also, find the g) a n+2 =−4a n+1 + 5a n for n ≥ 0, a 0 = 2, a 1 = 8
degree of those that are. 5. How many different messages can be transmitted in n mi-
a) a n = 3a n−2 b) a n = 3 croseconds using the two signals described in Exercise 19
2
c) a n = a d) a n = a n−1 + 2a n−3 in Section 8.1?
n−1
e) a n = a n−1 /n 6. How many different messages can be transmitted in n
f) a n = a n−1 + a n−2 + n + 3 microseconds using three different signals if one signal
g) a n = 4a n−2 + 5a n−4 + 9a n−7 requires 1 microsecond for transmittal, the other two sig-
3. Solve these recurrence relations together with the initial nals require 2 microseconds each for transmittal, and a
conditions given. signal in a message is followed immediately by the next
a) a n = 2a n−1 for n ≥ 1, a 0 = 3 signal?
b) a n = a n−1 for n ≥ 1, a 0 = 2 7. In how many ways can a 2 × n rectangular checkerboard
c) a n = 5a n−1 − 6a n−2 for n ≥ 2, a 0 = 1, a 1 = 0 be tiled using 1 × 2 and 2 × 2 pieces?
d) a n = 4a n−1 − 4a n−2 for n ≥ 2, a 0 = 6, a 1 = 8 8. A model for the number of lobsters caught per year is
e) a n =−4a n−1 − 4a n−2 for n ≥ 2, a 0 = 0, a 1 = 1 based on the assumption that the number of lobsters
f) a n = 4a n−2 for n ≥ 2, a 0 = 0, a 1 = 4 caught in a year is the average of the number caught in
g) a n = a n−2 /4 for n ≥ 2, a 0 = 1, a 1 = 0 the two previous years.