Solution for Section 8.1 Question 7

7. a)

b) S₀ = 1,  S₁ = 2,  S₂ = 3,  S₃ = 4,  S₄ = 5.

c) To build the required bit strings of length n in terms of the bit stings of length n-1 the following steps are taken, for each string of length n-1:

• if the string ends in a 0 (that is, it is the string of all 0's) then it can be extended by adding a 0 or it can be extended by adding a 1;
• if the string ends in a 1, then it can only be extended by adding a 1.

Using these two facts we see that a recurrence relation for S_n in terms of   S_n-1 is given by S_n = S_n-1 + 1 for all n1.

Hence the number of bit strings of length ten which do not contain the bit pattern 10 is S₁₀ = 11. 

Back to Section 8.1