Kenneth Rosen Edition 6th Exercise 7.1 Question 23 (Page No. 458)

Question

Find a recurrence relation for the number of bit strings of length n that contains a pair of consecutive 0s

Answer 1

There are three cases need to be dealt with here. First, from each string of length $n-1$ string, string of length $n$ can be created be appending $1$ (It will be $a'_{n}=a_{n-1}$). Second, from each string of length $n-2$, strings of length $n$ can be created by appending either $00$ or $10$  (it will be $a''_{n}=2a_{n-2}$). Finally, you can add $00$ to each string of length $n-2$ that are bereft of consecutive $0s$ (It will be $a'''_n = 2^{n-2}-a_{n-2}$)... Another.

$a_n = a'_n + a''_n + a'''_n$ is your answer.

Answer 2

You can solve it by formulating the recurrence-

Let T(N) be the recurrence relation for n length such strings

For n =1 we have  nothing

For n=2 we have 00

For n=3 we have  T(1)1  (Appending 1 to length n -1 strings which means Strings ending with 1 ) + 00(1) (Strings ending with 00)

For n=4 we have  T(3)1 (Strings ending with 1) + (2^(2)-T(2))00 ( This means length n -2 strings which do not have consecutive zeroes.)

For n=5= we have T(4)1 + (2^3-T(3))00

So for n=n We have T(n)=T(n-1)+ (2^(n-2)) - T(n-2)