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 March 21, 2019, 9:08 pm 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.