edited by
449 views

2 Answers

0 votes
0 votes

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.

edited by
0 votes
0 votes
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)

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Dec 10, 2018
385 views
this is an example taken from Rosen. but I’m unable to understand to understand the solution given therecan someone pls explain me in details
0 votes
0 votes
1 answer
3