For each integer n greaterthanorequalto 1, let r_n be the number of binary strin

Question

For each integer n greaterthanorequalto 1, let r_n be the number of binary strings of length n that do not contain three consecutive 1s. (i) Find r_1, r_2, r_3 and r_4. (ii) Find a recurrence for r_n that holds for all integers n greaterthanorequalto 4. Explain why your recurrence gives r_n. For each integer n greaterthanorequalto 5, let s_n be the number of binary strings of length n that do not contain three consecutive 1s, do not begin with 1 and end with two consecutive 1s, and do not begin with two consecutive 1s and end with 1. (iii) Find an expression for s_n in terms of r_1, r_2, ..., r_n - 1 that holds for all integers n greaterthanorequalto 5. Explain why your expression gives s_n.

Explanation / Answer

i) r1={0,1} =2

r2={00,11,10,01}=4

r3=2^3-1 since 1 belongs to(111) =7

r4= 2^4-3 since 3 belongs to {(1111,1110,0111)} =13

ii)for n>=4

originally we can put either 0 or 1 at the end so its recurrence is rn-1 + rn-1 =2 rn-1 .

now for n>=5 it is given it ends with 2 consecutive 1's and do not begin with 2 consecutive 1's so the string which cannot be part is 11111,10011,11011,10111 this 4 need to be subtracted from the recurrence relation so the relation becomes

rn= 2 rn-1 + rn-4

for all n>=4 there are always 4 string which need to be subtracted

iii)Sn= 2 r4 +r1

= 2( (2 * r3 ) +r0) +r1

= 2( ( 2* ( 2* r2)) +r0) +r1

= 8 r2 +2 r0 + r1

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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