__Solution set of Homework Assignment 5__

Section 5.1

18.a) Let a_{n} denote the number of bit strings of length n that contain three
consecutive 0s. The

number of bit strings of length n that have three 0s equals the number of bit strings of length

n-1 that contain three consecutive 0s with a 1 added to the end plus the number of bit strings

of length n-2 that contain three consecutive 0s with a 10 added to the end plus the number of

bit strings of length n-3 that contain three consecutive 0s with 100 added to the end plus the

number of bit strings of length n-3 with 000 added to the end. Thus,

a_{n} = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3}
for n ³ 3.

b) The initial conditions are a_{0} = a_{1} = a_{2} = 0.

c) a_{7} = 47

21.a) a_{n} = a_{n-1} + a_{n-2} for n ³
2.

b) The initial conditions are a_{0} = 1, a_{1} = 1.

c) a_{8} = 34.

22.a) Let a_{n} denote the number of ways to climb n stairs when a person
climbing the stairs can

take one, two, or three stairs at a time. Then a_{n} equals the number of ways
to climb n - 1 stairs

after he/she takes one stair at a time first plus the number of ways to climb n - 2 stairs after

he/she takes two stairs at a time first plus the number of ways to climb n - 3 stairs after he/she

takes three stairs at a time first. Thus,

a_{n} = a_{n-1} + a_{n-2} + a_{n-3} for n ³ 3.

b) The initial conditions are a_{0} = 1, a_{1} = 1, a_{2} = 2.

c) a_{8} = 81.

30.a) Let a_{n} denote the number of different ways a bus driver can pay a toll
of n cents. The

number of different ways a bus driver pays a toll of n cents equals the number of different

ways he/she pays a toll of n - 5 cents after throwing one nickel first plus the number of

different ways he/she pays a toll of n - 10 cents after throwing one dime first. Since he/she

pays all tolls, using only nickels and dimes, we can assume n is a multiple of 5.

Therefore,

a_{n} = a_{n-5} + a_{n-10} for n ³
10, where n is a multiple of 5.

The initial conditions are a_{0} = 1, a_{5} = 1.

b) a_{45} = 55.

34.Let a_{n} denote the number of bit sequences of length n with an even number
of 0s. There are

two ways to form a valid string with n bits from a string with one fewer bit. First, a valid string

of n digits can be obtained by appending a valid string of n – 1 bits with 1. Hence, a valid

string with n bits can be formed in this manner in a_{n-1} ways. Second, a
valid string of n bits can

be obtained by appending a 0 to a string length n – 1 that is not valid. The number of ways that

this can be done equals the number of invalid (n – 1)-bit strings. Since there are
2^{n-1 }strings of

length n – 1, and a_{n-1 }are valid, there are 2^{n-1} – a_{n-1}
valid n-bit strings obtained by appending an

invalid string of length n – 1 with a 0. Therefore

a_{n} = a_{n-1} + (2^{n-1} – a_{n-1}) = 2^{n-1}
for n ³ 2.

But since this doesn’t include the previous terms, it is not a recurrence relation. Thus we need

to convert this into a recurrence relation.

a_{n} = 2a_{n-1} for n ³ 2.

a_{1} = 1.