Explore BrainMass

Explore BrainMass

    Recurrence relations - initial conditions

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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?

    © BrainMass Inc. brainmass.com June 4, 2020, 12:50 am ad1c9bdddf

    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.