Make a list of all bit strings of lengths zero one two

Question

Queston: Counting Strings:

a. Make a list of all bit strings of lengths zero, one, two, three, and four that do not contain the bit pattern 111

b. For each integer n ≥ 0, let dn = the number of bit strings of length n that do not contain the bit pattern 111. Find d₀, d₁, d₂, d₃, and d₄.

c. Find a recurrence relation for d₀, d₁, d₂,... .

d. Use the results of parts (b) and (c) to find the number of bit strings of length five that do not contain the pattern 111.