Let f(n) be the number of bit strings of length n that contain three consecutive

Question

Let f(n) be the number of bit strings of length n that contain three consecutive 0's. Note: a string that contains four or more consecutive 0's is also considered to contain three consecutive 0's. We want to define f(n) recursively. we consider n >= 5. We want to express f(n) recursively in terms of f(n-1); f(n-2),...... Here are some hints: (Step 1) If x is a bit string of length n-1 that contains three consecutive 0's, then extending it by a bit 0 or bit 1 will give rise to a string of length n that again contains three consecutive 0's. (Step 2) Consider a bit string x of length n that contains three consecutive 0's, but is not derived by Step 1. Next, answers the following two questions about such string x.

Q1.What can you say about the first n - 4 bits of x? Why can't the first n-4 bits of x contain three consecutive 0's? How many different such prefixes of x with length n - 4 could there be?

Explanation / Answer

As mentioned in the question one of the cases is when the bit string of length n-1 contains three consecutive 0's and last one can be 0 or 1.so by this the recurrence relation that comes out from it is

f(n)=2*f(n-1) + something else -- (1)

i hope this much must be clear

then the second set of strings should not be derived from 1.

So for that we consider set of strings of length n-4 which will not contain 3 consecutive 0's and append 1000 to all these strings.this will make them containing 3 consecutive 0's we cant take 000 or 0001 because that would count in the first case itself.So another set of string containing 3 consecutive 0's can be found out by f(n-4)' which means count of string not having 3 consecutive 0's in strings of length n-4 -- (1st part answer and second part answer)

hence the recurrence

f(n) = something + f(n - 4)' - (2)

combining (1) and (2) we have

f(n) =2*f(n-1) + f(n-4)' - (3)

if f(n) is the number of strings having 3 consecutive 0's then f(n)' are the number of strings not having 3 consecutive 0's.

then it is obvious that

f(n)' = 2n - f(n) - (4)

so f(n-4)' = 2n-4 - f(n-4) - (5)

hence with the help of (4) and (5),(3) can be written as

f(n) = 2*f(n-1) + 2n-4 - f(n-4)

which is the required recurrence relation.

f(0)=f(1)=f(2) = 0,

f(3) = 1

f(4) = 2*f(3)+24 - 4- f(0) =3

f(5) = 2*f(4) + 25-4 - f(1)=2*3 + 2 = 8

and so on

If you liked the answer do not forget to rate.All the best :)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.