Question

6. (10 points) Let Sn be the number of n-bit strings of O's and 1's that avoid the pattern "11". Find the recurrence relation for sm and find the solution for this recurrence relation.

Answer 1

The least value of n for the series to be recursive is 3. Because to predict a series, we need atleast three elements.

Now, we will approximate the Series based on the Values of n i.e.

For n =1 :

Strings can be : (0,1)

So, Total Number of Strings : 2

For n =2 :

Strings can be : (00, 01, 10)

So, Total Number of Strings : 3

For n =3 :

Strings can be : (000, 001, 010, 100, 101)

So, Total Number of Strings : 5

For n =4 :

Strings can be : (0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001)

So, Total Number of Strings : 8

and so on...

Now, take into Consideration, all the Total Number of Strings i.e. 2,3,5,8

If we look at this Series, it make a Normal Fibonacci Series.

So, the general Formula of a Fibonacci Series is our Required Ans i.e.

Sn = Sn n-1 + Sn -2

Please UpVote. It Helps. Thank You.