Page 532 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 511

b) What are the initial conditions? ∗ 17. a) Find a recurrence relation for the number of ternary
c) How many bit strings of length seven contain two strings of length n that do not contain consecutive
consecutive 0s? symbols that are the same.
8. a) Find a recurrence relation for the number of bit strings b) What are the initial conditions?
of length n that contain three consecutive 0s. c) How many ternary strings of length six do not contain
b) What are the initial conditions? consecutive symbols that are the same?
c) How many bit strings of length seven contain three
∗∗ 18. a) Find a recurrence relation for the number of ternary
consecutive 0s?
strings of length n that contain two consecutive sym-
9. a) Find a recurrence relation for the number of bit strings bols that are the same.
of length n that do not contain three consecutive 0s. b) What are the initial conditions?
b) What are the initial conditions?
c) How many ternary strings of length six contain con-
c) How many bit strings of length seven do not contain
secutive symbols that are the same?
three consecutive 0s?
19. Messages are transmitted over a communications channel
∗ 10. a) Find a recurrence relation for the number of bit strings
of length n that contain the string 01. using two signals. The transmittal of one signal requires
b) What are the initial conditions? 1 microsecond, and the transmittal of the other signal re-
quires 2 microseconds.
c) How many bit strings of length seven contain the
string 01? a) Find a recurrence relation for the number of differ-
ent messages consisting of sequences of these two
11. a) Find a recurrence relation for the number of ways to
climb n stairs if the person climbing the stairs can take signals, where each signal in the message is imme-
one stair or two stairs at a time. diately followed by the next signal, that can be sent
b) What are the initial conditions? in n microseconds.
b) What are the initial conditions?
c) In how many ways can this person climb a flight of
eight stairs? c) How many different messages can be sent in 10 mi-
croseconds using these two signals?
12. a) Find a recurrence relation for the number of ways to
climb n stairs if the person climbing the stairs can take 20. A bus driver pays all tolls, using only nickels and dimes,
one, two, or three stairs at a time. by throwing one coin at a time into the mechanical toll
b) What are the initial conditions? collector.
c) In many ways can this person climb a flight of eight a) Find a recurrence relation for the number of different
stairs? ways the bus driver can pay a toll of n cents (where
A string that contains only 0s, 1s, and 2s is called a ternary the order in which the coins are used matters).
string. b) In how many different ways can the driver pay a toll
13. a) Find a recurrence relation for the number of ternary of 45 cents?
strings of length n that do not contain two consecutive 21. a) Find the recurrence relation satisfied by R n , where R n
0s. is the number of regions that a plane is divided into
b) What are the initial conditions? by n lines, if no two of the lines are parallel and no
c) How many ternary strings of length six do not contain three of the lines go through the same point.
two consecutive 0s? b) Find R n using iteration.
14. a) Find a recurrence relation for the number of ∗
22. a) Find the recurrence relation satisfied by R n , where R n
ternary strings of length n that contain two is the number of regions into which the surface of a
consecutive 0s. sphere is divided by n great circles (which are the in-
b) What are the initial conditions? tersections of the sphere and planes passing through
c) How many ternary strings of length six contain two the center of the sphere), if no three of the great circles
consecutive 0s? go through the same point.
∗ 15. a) Find a recurrence relation for the number of ternary b) Find R n using iteration.
strings of length n that do not contain two consecutive
∗ 23. a) Find the recurrence relation satisfied by S n , where S n
0s or two consecutive 1s.
is the number of regions into which three-dimensional
b) What are the initial conditions?
space is divided by n planes if every three of the planes
c) How many ternary strings of length six do not contain meet in one point, but no four of the planes go through
two consecutive 0s or two consecutive 1s?
the same point.
∗ 16. a) Find a recurrence relation for the number of ternary b) Find S n using iteration.
strings of length n that contain either two consecutive
0s or two consecutive 1s. 24. Find a recurrence relation for the number of bit sequences
of length n with an even number of 0s.
b) What are the initial conditions?
c) How many ternary strings of length six contain two 25. How many bit sequences of length seven contain an even
consecutive 0s or two consecutive 1s? number of 0s?