Solution set of Homework Assignment 5

Section 5.1

18.a) Let an 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,

an = an-1 + an-2 + an-3 + 2n-3 for n 3.

b) The initial conditions are a0 = a1 = a2 = 0.

c) a7 = 47

21.a) an = an-1 + an-2 for n 2.

b) The initial conditions are a0 = 1, a1 = 1.

c) a8 = 34.

22.a) Let an 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 an 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,

an = an-1 + an-2 + an-3 for n 3.

b) The initial conditions are a0 = 1, a1 = 1, a2 = 2.

c) a8 = 81.

30.a) Let an 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,

an = an-5 + an-10 for n 10, where n is a multiple of 5.

The initial conditions are a0 = 1, a5 = 1.

b) a45 = 55.

34.Let an 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 an-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 2n-1 strings of

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

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

an = an-1 + (2n-1 – an-1) = 2n-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.

an = 2an-1 for n 2.

a1 = 1.