1 5 Marks Let Fn Be The Number Of Binary Strings Of Length N Which Do Not Contain A Factor 111 A And Have Final Digit 1 (35.16 KiB) Viewed 21 times
(a) What is f0,f1,f2,f3,f4?
b) Find a recursive formula for fn (Hint: every string counted
by fnmust end in 0, so think about all the possible endings:
00,10,.... Hint 2: if a string
ends in 10, then it ends in either 010 or 110. If it ends in 110,
the digit before must be ....)
(1.5 marks) Let fn be the number of binary strings of length n which do not contain a factor 111 a and have final digit 0. (a) What is fo, f1, f2, f3, f4? 5 (b) Find a recursive formula for fm
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!