# Recurrence relations - initial conditions

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?

https://brainmass.com/math/recurrence-relation/recurrence-relations-initial-conditions-363478

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