A) Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0s.
b) What are the initial conditions?
c) How many bit strings of length seven contain three consecutive 0s?
Please see the attached PDF document for a more readable version of this response.
Since we have to find a recurrence relation, the first thing we do is assume that we "know" the value of the function required (here, the function giving the number of bit strings of length n that contain three consecutive 0s) for a certain number of values of n. That is, we assume we know the values of a_1, a_2, ... a_n.
Then, using these, we calculate the value of a_(n+1).
Suppose we are given a string of length n, which already contains three consecutive 0s. Then we can add either a 0 or a 1 at its end to get a string of length n + 1, which contains three consecutive 0s.
This means for each string of length n which contains three consecutive 0s, there are two strings of length n + 1 which contain three consecutive 0s (one obtained by adding a 0 at the ...
The initial conditions are inspected in this case.