1. *For n 2 1, let f(n) count the number of binary strings of length n that do n
ID: 3199225 • Letter: 1
Question
1. *For n 2 1, let f(n) count the number of binary strings of length n that do not contain 011 as a substring. Among these strings, let g(n) count those which do not end in 01. (a) Express f(n) in terms of f (n - 1) and g(n -1). For what range of n is your expression valid? (b) Express g(n) in terms of f(n -1) and g(n -1). For what range of n is your expression valid? (c) Find f(1) and 9(1). Then, use parts (a) and (b) to compute f(7). Hint: For both (a) and (b), consider the last character of the string. Note that the coefficient of f(n-1) or g(n 1) may be zero.]Explanation / Answer
Consider a string of length n that do not contain 011. Consider the string formed by forst n-1 digits clearly it does not contain 011 digits if it does not end in 01 than attaching either a 0 or 1 will give a string of length n which does not contain 011. F(n-1)-g(n-1) denote the number of string of length n-1 which do not contain 011 but end with 01. appending 0 to this string gives a string of length n which does not contain 011
F(n) = g(n-1)*2 + (F(n-1)-g(n-1))
= F(n-1) + g(n-1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.