Hint for Section 8.1 Question 7

7. To write out bit strings which do not contain the bit pattern 10,  if you are working from left to right, as soon as you write down a 1, the rest of the bits must all be 1's as well.

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.

Use these two facts to write a recurrence relation for S_n in terms of   S_n-1.

Back to Section 8.1
Full solution