(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
Posted: Fri Apr 29, 2022 10:43 am
- 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 23 times
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