Problem 1: Let R for n 0, be the number of binary strings of length n that do no
ID: 3209689 • Letter: P
Question
Problem 1: Let R for n 0, be the number of binary strings of length n that do not contain 11 and 101 For example, R6, because there are six binary strings of length 4 that satisfy this condition: 0000 0001 0010 0100 1000 1001 (a) Give the values of Rn fo0,1,2,3,5. For each value list the strings that satisfy the required condition, as in the example above. (Note: the standard notation for the empty string is e.) (b) Derive the recurrence equation for Rn. You need to give a clear and complete justification for your equation. (You do not need to solve the recurrence.) iVeExplanation / Answer
R0 contains nothing.i.e empty string epsilon
R1 is trivial with 0 and 1 So numbers = 2
R2 contains 00 10 01 Hence numbers = 3
R3 contains 000 001 010 100 . Hence numbers= 4
R4 contains 6 numbers as given.
R5 contains
00000 00010 00100 10000 10001 10010 00001 01000 01001There are 9 numbers.
R4 contains 6 numbers.
We can add to the right end 0 and can have 6 numbers satisfying the condition. Next is we can add 1s only to 3 numbers in the list. Hence we have 6+3 =9 numbers for R5.
b) In general we have
Rn+1 = Rn+(n/2) for all n>=2.