Question

find a recurrence relation for the number of bit strings of length n that contain the string 10. What are the initial conditions? How many bit strings of length eight contain the string 10

Answer 1

Let be the number of such strings of length . Then and . Let and consider such a string of length . Write this string as . We need to consider the following cases:

Case I: If then must contain somewhere in it, and if contains somewhere in it, then with is a valid such string of length . Thus, number of valid length string with is .

Case II: If then is valid if and only if for some . There are such strings. Thus, number of valid length string with is .

Since these two cases are mutually exhaustive and accounts for all possibilities, we conclude that

Thus, the recurrence with initial conditions are

We find

Thus, there are such strings of length .