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?

Solution Preview

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 ...

Solution Summary

The initial conditions are inspected in this case.

... either dies or is taken by a poacher each year and only 5 new jabby birds are born, write a recurrence relation and initial conditions describing the number jn ...

... an = 2nan - 1. 3..Solve the given recurrence relation for the initial condition given. ... 4. Solve the given recurrence relation for the initial condition given. ...

... a ternary string a) find a recurrence relation for the number of ternary strings that contain two consecutive 0s b) what are the initial conditions c) how many ...

... this formula obeys the recurrence (1) as well as the initial conditions (2). We ... Thus we see that the recurrence relation (1) is also satisfied, verifying (3). ...

1) Use the method of Iteration to find a formula expressing S(n) as a function of n for the given recurrence relation and initial condition: S(n) = S(n-1) - 3 ...