Show All Solutions

Rosen, Discrete Mathematics and Its Applications, 6th edition

Extra Examples
Section 7.1Recurrence Relations
Page references correspond to locations of Extra Examples icons in the textbook.

p.451, icon at Example 3

#1. Find a recurrence relation (and initial condition) for each of the following:
(a) the number of strings of length n of letters of the alphabet.
(b) the number of strings of length n of letters of the alphabet, if no adjacent letters can be the same.
(c) the number of strings of length n of letters of the alphabet with no repeated letters.
See Solution

Solution:
(a) Let an equal the number of strings of length n of letters of the alphabet. We can obtain any such string
by taking a string s of length n 1 and appending a letter to the end of s. This can be done in 26 ways.
Therefore, an = 26an1 . The initial condition is a1 = 26.
(b) Let bn equal the number of strings of length n of letters of the alphabet with no adjacent letters identical.
Each such string can be obtained from a string s of length n 1 by taking s and appending to it a letter
that is dierent from the last letter of s. Because there are 25 letters that can be appended, there are 25
ways to extend s to a string of length n. Therefore, bn = 25bn1. The initial condition is b1 = 26.
(c) Let cn equal the number of strings of length n of letters of the alphabet with no repeated letters. Each
such string can be obtained from a string s of length n 1 by taking s and appending to it a letter that is
dierent from each of the letters of s. Because there are n 1 letters used in s, there are 26 (n 1) = 27 n
letters available to be appended to s. Therefore, cn = (27 n)cn1 . The initial condition is c1 = 26. Note
that c27 = (27 27)c26 = 0 because there are only 26 letters in the alphabet. Likewise, the recurrence
relation yields c28 = c29 = . . . = 0.

p.451, icon at Example 3

1 1 1 1
1
#2. Find a recurrence relation for the sequence 1, , , , , . . . , which is given by the formula an =
3 5 7 9
2n + 1
for n = 0, 1, 2, 3, . . . .
See Solution

Solution:
We will try to relate an =

1
1
1
and an1 =
=
to each other:
2n + 1
2(n 1) + 1
2n 1
an =

But we can rewrite an1 =

1
1
=
.
2n + 1
(2n 1) + 2

1
1
as 2n 1 =
.
2n 1
an1

Therefore,
an =

1
=
2(n 1) + 2

1
1
an1

=
+2
1

an1
1
=
.
1 + 2an1
1 + 2an1
an1

Thus, a recurrence relation for the given sequence is

an =

an1
,
1 + 2an1

with initial condition a0 = 1.

Alternately, we could write an =
second recurrence relation

1
2n 1
2n 1
1
2n 1
1
=

=
an1 , obtaining a
2n + 1
2n + 1 2n + 1
2n + 1 2n + 1
2n + 1
an =

2n 1
an1 ,
2n + 1

with initial condition a0 = 1.

p.451, icon at Example 3

#3. Suppose bn = 2bn1 + n 2n and b0 = 5.
(a) Find bn1 in terms of bn2 .
(b) Find bn in terms of bn2 .
(c) Find bn in terms of bn3 .
(d) Use parts (b) and (c) to conjecture a formula for bn .
See Solution

Solution:
(a) The recurrence relation for bn doubles the previous term (which is 2bn1 ), adds the subscript number of
bn (which is n), and subtracts 2 raised to the power of the subscript of bn (which is 2n ).
The term bn1 is obtained in the same way: double the previous term (which is 2bn2 ), add the subscript
number of bn1 (which is n 1), and subtract 2 raised to the power of the subscript of bn1 (which is 2n1 ).
Therefore bn1 = 2bn2 + (n 1) 2n1 .
(b) To obtain bn in terms of bn2 , we rst use the recurrence relation to obtain bn in terms of bn1 and then
use part (a) to obtain bn1 in terms of bn2 :
bn = 2bn1 + n 2n
= 2[2bn2 + (n 1) 2n1 ] + n 2n
= 22 bn2 + (n 1) + n 2n1 2n .
(c) To obtain bn in terms of bn3 , we can use the recurrence equation for bn2 and part (b). The recurrence
relation for bn2 is bn2 = 2bn3 + (n 2) 2n2 . Substituting for bn2 into the result in part (b), we have
bn = 22 bn2 + (n 1) + n 2n1 2n
= 22 [2bn3 + (n 2) 2n2 ] + (n 1) + n 2n1 2n
= 23 bn3 + (n 2) + (n 1) + n 2n2 2n1 2n .
(d) Mentally continuing the pattern in part (c), it seems reasonable to guess that the rst term becomes
2n b0 , the sum (n 2) + (n 1) + n becomes 1 + 2 + 3 + + (n 2) + (n 1) + n, and the sum of the powers
of 2 being subtracted becomes 21 22 23 2n1 2n1 2n . Thus, it is reasonable to conjecture
that
bn = 2n b0 + [1 + 2 + 3 + + (n 2) + (n 1) + n] [21 + 22 + 23 + + 2n1 + 2n1 + 2n ]
n(n + 1)
2n+1 ,
= 5 2n +
2
2

where summation formulas were used at the last step to replace 1 + 2 + 3 + + (n 2) + (n 1) + n and
21 + 22 + 23 + + 2n1 + 2n1 + 2n .
Note: You can check that this is correct by substituting the formula for bn and bn1 into the given recurrence
relation and showing that both sides of the recurrence relation are equal.

p.451, icon at Example 3

#4. Solve: an = 3an1 + 1, a0 = 4, by substituting for an1 , then an2 , etc.
See Solution

Solution:
Beginning with an = 3an1 + 1 and substituting for an1 , then an2 , then an3 , etc., yields:
an = 3an1 + 1
= 3(3an2 + 1) + 1
= 32 an2 + 3 1 + 1
= 32 (3an3 + 1) + 3 1 + 1
= 33 an3 + 32 1 + 3 1 + 1
..
.
= 3n a0 + (3n1 + 3n2 + + 32 + 3 + 1)
3n 1
= 4 3n +
2
9 n 1
= 3
2
2
1
3n+2
.
=
2
2

p.451, icon at Example 3

#5. Find a formula for the recurrence relation an = 2an1 + 2n , a0 = 1, using a recursive method.
Solution:

See Solution

an = 2an1 + 2n
= 2(2an2 + 2n1 ) + 2n = (22 an2 + 22n1 ) + 2n = (22 an2 + 2n ) + 2n = 22 an2 + 22n
= 22 (2an3 + 2n2 ) + 22n = (23 an3 + 22 2n2 ) + 22n = (23 an3 + 2n ) + 22n = 23 an2 + 32n .
At this stage it would be reasonable to guess that if we continue this process we will obtain:
an = 2n a0 + n 2n = 2n 1 + n 2n = (n + 1)2n .
Therefore, an = (n + 1)2n is a formula for the given sequence.
We can verify that this formula is correct by substituting an = (n + 1)2n and an1 = n2n1 into the original
recurrence relation and checking that an equality results.:
3

2an1 + 2n = 2(n2n1 ) + 2n = n2n + 2n = (n + 1)2n = an .

p.451, icon at Example 3

#6. You begin with $1000. You invest it at 5% compounded annually, but at the end of each year you
withdraw $100 immediately after the interest is paid.
(a) Set up a recurrence relation and initial condition for the amount you have after n years.
(b) How much is left in the account after you have withdrawn $100 at the end of the third year?
(c) Find a formula for an .
(d) Use the formula to determine how long it takes before the last withdrawal reduces the balance in
the account to $0.
See Solution

Solution:
(a) For n > 0, let an be the amount in the account at the end of year n; i.e., just after the interest has been
added to the account and the $100 has been withdrawn. Then an is equal to the amount from the previous
year (an1 ) plus the interest earned (0.05an1 ) minus the $100 withdrawal. That is,
an = an1 + 0.05an1 100 = 1.05an1 100, if n > 0, a0 = 1000.
(b) Using the recurrence relation yields
a1 = 1050 100 = 950
a2 = 1.05a1 100 = 1.05(950) 100 = 997.50 100 = 897.50
a3 = 1.05a2 100 = 1.05(897.50) 100 = 942.38 100 = 842.38
Thus, the answer is $842.38.
(c) To develop a formula, note that
an = 1.05an1 100,
an1 = 1.05an2 100,
an2 = 1.05an3 100,
..
.
Therefore
4

an = 1.05an1 100
= 1.05(1.05an2 100) 100
= 1.052 an2 (1.05100) 100
= 1.052 (1.05an3 100) (1.05100) 100
= 1.053 an3 (1.052 100) (1.05100) 100
..
.
= 1.05n a0 (1.05n1 100) (1.05n2 100) (1.052 100) (1.05100) 100
= 1.05n 1000 100(1.05n1 + 1.05n2 + + 1.052 + 1.05 + 1)
1.05n 1
= 1.05n 1000 100
1.05 1
= 1.05n 1000 2000(1.05n 1)
= 2000 1.05n 1000
and hence a formula for an is an = 2000 1.05n 1000.
(d) Using various values of n in the formula for an yields a14 = 20.07 and a15 = 78.93. Hence, at the
end of the 15th year the balance will be 1.05 20.07 = 21.07 before a withdrawal is made; if this amount is
withdrawn, the balance will become $0. (Alternately, we could solve the equation 2000 1.05n 1000 = 0
for n and obtain n as the solution.)

p.451, icon at Example 3

#7. Find a recurrence relation for the number of strings of letters of the ordinary alphabet that do not
have adjacent vowels.
See Solution

Solution:
Let us call a string of letters of the alphabet good if it has no adjacent vowels. Let an be the number of
strings of length n of letters of the alphabet that do not have adjacent vowels.
The set of all good strings of length n is the union of the following two disjoint sets
A: the set of good strings of length n that end with a consonant, and
B: the set of good strings of length n that end with a vowel.
Each string in A can be obtained from a good string of length n 1 by adding any consonant at the end of
the string. Thus, |A| = 21 an1 .
Each string in B ends with a vowel. In this case we know that that second letter from the end must be
a consonant (otherwise the string would have adjacent vowels). Thus, each string in B is a good string
of length n 2 followed by a consonant (in the second last position) and a vowel at the end. Therefore,
|B| = 5 21 an2 .
Because A and B are disjoint, the set of all good strings of length n is their sum, |A| + |B|. That is,
an = 21 an1 + 105 an2 .
The two initial conditions are obtained by counting the number of good strings of lengths 1 and 2: a1 = 26
because any string of one of the 26 letters of the alphabet cannot have adjacent vowels; a2 = 262 52 = 651
(we take all strings of length 2 and subtract those with two vowels).
5

p.451, icon at Example 3

#8. You have two distinct parallel lines L1 and L2 . You keep adding additional lines, L3 , L4 , . . . , with
none parallel to L1 or L2 or to each other, and no three passing through the same point.
(a) Find a recurrence relation and initial condition(s) for rn , which is dened to be the number of regions
into which the plane is divided by the lines L1 , L2 , . . . , Ln .
(b) Find a formula for the number of regions into which the plane is divided by L1 , L2 , . . . , Ln .
See Solution

Solution:
(a) The recurrence relation is rn = rn1 + n (n > 2), with initial condition r2 = 3. To see this, note that
line Ln must cut each of the previous n 1 lines in exactly one point. This in eect divides Ln into n
segments, each of which divides an existing region into two parts. Therefore, rn = rn1 + n.
(b) Proceeding inductively:
r2 = 3,
r3 = r2 + 3 = 3 + 3,
r4 = r3 + 4 = 3 + 3 + 4,
r5 = r4 + 5 = 3 + 3 + 4 + 5,
r6 = r5 + 6 = 3 + 3 + 4 + 5 + 6.
This suggests that
rn = 3 + (3 + 4 + + n)
= (1 + 2) + (3 + 4 + + n)
= 1 + 2 + 3 + + n
=

n(n + 1)
.
2

To verify that this guess is correct, take rn = rn1 + n and substitute

n(n + 1)
(n 1)n
for rn and
for
2
2

(n 1)n
n(n + 1)
=
+ n, which is true because the right side simplies to give the left side:
2
2
2
(n 1)n + 2n
n +n
n(n + 1)
(n 1)n
+n=
=
=
.
2
2
2
2

rn1 , obtaining

p.451, icon at Example 3

#9. This is a variation on Fibonaccis rabbit sequence. We begin with one pair of newborn rabbits. Once a
pair is two months old, the pair has two pairs of ospring, and continues to have two pairs of ospring each
month thereafter. Give a recurrence relation and initial condition(s) for the sequence fn , where fn is equal
to the number of pairs of rabbits alive at the end of the nth month (after the ospring are born). Assume
that the rabbits never die during the period being considered.
See Solution

Solution:
The number of pairs at the end of n months (fn ) is equal to the number of pairs alive one month earlier
(fn1 ) plus the number of newborn pairs. But each pair of rabbits alive two months earlier gives birth to
two pairs of newborn rabbits. Therefore, there are 2fn2 pairs of newborn rabbits. Hence
fn = fn1 + 2fn2 , f (1) = 1, f (2) = 3.
6

p.451, icon at Example 3

#10. Here is another variation on Fibonaccis rabbit sequence. We begin with one pair of newborn rabbits.
At the end of each month a new pair of newborn rabbits is added to the population. Once any pair is
two months old, the pair has one pair of ospring and continues to have one pair of ospring each month
thereafter. Give a recurrence relation and initial condition(s) for the sequence fn , where fn is equal to the
number of pairs of rabbits alive at the end of the nth month (after the rabbits have given birth and the
newborn pair has been introduced). Assume that the rabbits never die during the period being considered.
See Solution

Solution:
The number of pairs at the end of n months (fn ) is equal to 1 (the newborn pair added) plus the number
of pairs alive one month earlier (fn1 ) plus the number of newborn pairs (which is equal to the number of
pairs alive two months earlier, fn2 . Thus
fn = 1 + fn1 + fn2 , f (1) = 2, f (2) = 4.

p.451, icon at Example 3

#11. Here is a third variation on Fibonaccis rabbit sequence. We begin with one pair of newborn rabbits.
Once the pair is three months old, the pair has one pair of ospring, and continues to have one pair of ospring
every other month thereafter. Give a recurrence relation and initial condition(s) for the sequence fn , where fn
is equal to the number of pairs of rabbits alive at the end of the nth month (just after any ospring are
born). Assume that the rabbits never die during the period being considered.
See Solution

Solution:
The number of pairs alive at the end of n months (fn ) is equal to the number of pairs alive one month earlier
(fn1 ) plus the number of pairs of newborn rabbits. To determine the number of newborn pairs, we need to
know the number of pairs born three months earlier, ve months earlier, seven months earlier, etc. But, for
example, the number of pairs born three months before month n is equal to fn3 fn4 and the number of
pairs born ve months before month n is equal to fn5 fn6 .
Thus,
fn = fn1 + number of pairs born in month n
= fn1 + (fn3 fn4 ) + (fn5 fn6 ) + (fn7 fn8 ) +
where the sum continues as long as the subscripts are positive. Similarly,
fn1 = fn2 + number of pairs born in month n 1
= fn2 + (fn4 fn5 ) + (fn6 fn7 ) + (fn8 fn9 ) + .
Substitute fn1 from the second equation into the rst equation. Almost all terms cancel and we obtain
fn = fn2 + fn3 ,
with f (1) = 1, f (2) = 1, f (3) = 2.

p.451, icon at Example 3

#12. (Problem A1 from the 1990 William Lowell Putnam Mathematics Competition)
Here are the rst ten terms of an innite sequence:
2, 3, 6, 14, 40, 152, 784, 5168, 40567, 363392.
(a) Find a formula for an innite sequence a0 , a1 , a2 , a3 , . . . such that the rst ten terms of the sequence are
the ones given here. (Hint: consider the sum of two rapidly increasing sequences.)
(b) Show that the sequence in (a) satises the recurrence relation
an = (n + 4)an1 4nan2 + (4n 8)an3 .
See Solution

Solution:
(a) The sequence increases rapidly, which suggests the possibility that the formula may involve an exponential
function cn . If we look for 2n in each term, we nd the the rst few terms are:
20 + 1, 21 + 1, 22 + 2, 23 + 6, 24 + 24, 25 + 120, 26 + 720, 27 + 5040 .
The second term in each sum is a factorial, yielding
20 + 0!, 21 + 1!, 22 + 2!, 23 + 3!, 24 + 4!, 25 + 5!, 26 + 6!, 27 + 7! .
Thus, an = 2n + n! is one such formula.
(b) We need to show that an = (n + 4)an1 4nan2 + (4n 8)an3 is satised by the sequence an = 2n + n!.
That is,
2n + n! = (n + 4)[ 2n1 + (n 1)! ] 4n[ 2n2 + (n 2)! ] + (4n 8)[ 2n3 + (n 3)! ].
The right side can be simplied as follows:
(n + 4)[ 2n1 + (n 1)! ] 4n[ 2n2 + (n 2)! ] + (4n 8)[ 2n3 + (n 3)! ]
= n2n1 + 4 2n1 4n2n2 + 4n2n3 8 2n3 +
n(n 1)! + 4(n 1)! 4n(n 2)! + (4n 8)(n 3)!
= n2n1 + 2n+1 n2n + n2n1 2n + n! + 4(n 1)! 4n(n 2)! + (4n 8)(n 3)!
= n2n + 2n+1 n2n 2n + n! + 4(n 1)! 4n(n 2)! + (4n 8)(n 3)!
= 2n+1 2n + n! + 4(n 1)! 4n(n 2)! + (4n 8)(n 3)!
= 2n + n! + 4(n 1)! 4n(n 2)! + (4n 8)(n 3)!
= 2n + n! + 4(n 1)! 4n(n 2)! + 4(n 2)!
= 2n + n! + 4(n 1)! + (4 4n)(n 2)!
= 2n + n! + 4(n 1)! 4(n 1)(n 2)!
= 2n + n! + 4(n 1)! 4(n 1)!
= 2n + n!.

p.451, icon at Example 3

#13. Suppose a chess king is placed on the lower left square of an m n chessboard (that is, a rectangular
board with m rows and n columns). Let M (m, n) be equal to the number of paths that a king can use
moving from the lower left corner to the upper right corner of an m n board, with the restriction that each
move is either up, to the right, or diagonally up and to the right.
(a) Find a recurrence relation and initial condition(s) for M (m, n).
8

(b) Find the number of ways in which the king can move from the lower left square to the upper right
square on a 5 5 chessboard.
See Solution

Solution:
(a) In order for the king to reach the upper right square, the kings last move must be from one of the
following three squares: the square immediately below the corner square, the square immediately to the left
of the corner square, or the square diagonally down and to the left of the corner square. The number of
ways in which the king could have arrived at each of these three squares is M (m, n 1), M (m 1, n), and
M (m 1, n 1), respectively (assuming that m > 1 and n > 1). Therefore,
M (m, n) = M (m, n 1) + M (m 1, n) + M (m 1, n 1),
with initial conditions M (1, 1) = M (2, 1) = M (1, 2) = 1.
(b) First note that M (k, 1) = M (1, k) = 1 for all k > 1 and M (j, k) = M (k, j) for all j and k (by symmetry).
The following steps use the recurrence relation to nd M (5, 5):
M (2, 2) = M (2, 1) + M (1, 2) + M (1, 1) = 1 + 1 + 1 = 3
M (2, 3) = M (3, 2) = M (1, 3) + M (2, 2) + M (1, 2) = 1 + 3 + 1 = 5
M (3, 3) = M (3, 2) + M (2, 3) + M (2, 2) = 5 + 5 + 3 = 13
M (2, 4) = M (4, 2) = M (1, 4) + M (2, 3) + M (1, 3) = 1 + 5 + 1 = 7
M (2, 5) = M (5, 2) = M (1, 5) + M (2, 4) + M (1, 4) = 1 + 7 + 1 = 9
M (3, 4) = M (4, 3) = M (3, 3) + M (2, 4) + M (3, 2) = 13 + 7 + 5 = 25
M (3, 5) = M (5, 3) = M (4, 3) + M (5, 2) + M (2, 4) = 25 + 9 + 7 = 41
M (4, 4) = M (4, 3) + M (3, 4) + M (3, 3) = 25 + 25 + 13 = 63
M (4, 5) = M (5, 4) = M (4, 4) + M (3, 5) + M (3, 4) = 63 + 41 + 25 = 129
M (5, 5) = M (5, 4) + M (4, 5) + M (4, 4) = 129 + 129 + 63 = 321.
Therefore, M (5, 5) = 321.
This is shown in the following table, where, beginning from the lower left corner, each square has as its value
the sum of the numbers in the squares directly below, to the left, and diagonally below on the left.
1

41

129 321

25

63 129

13

25

41