Consider the set of binary strings (i.e. made of zeros and one's) that do not contain the substring 11 (i.e. 1 is never followed
by another 1 in the string). Suppose that T(n) is the number of such strings with length n. A string of length n has one of two forms. It might start with a 0, in which case the rest of the string can be anything that doesn't contain 11. Or it might start with a 1, in which case the next character must be a 0, and the remaining n-2 characters can be any string that doesn't contain 11. So we can set up the following recursive definition for T(n): T(1) 2 T(2)3 T(n) = T(n-1 ) + T(n-2) Now, consider the set of strings whose characters are a, b, and c which never contain the sequences bb or bc. For example, aba and cab are in the set, but abb and cbc are not. If S(n) is the number of strings of this type with length n, then S(1) 3 and S(2)7. How should we write the recursive part of the definition for S(n)? a. S(n) 3S(n-1)+ 7S(n-2)
b. S(n) as(n-1)+ bs(n-2) °
C. S(n) = S(n-1 ) + 2S(n-2)
d. S(n) acS(n-1) +bbS(n-2)
e. S(n) S(n-1) S(n-2) S(n-3)
f. S(n) 2S(n-1) + S(n-2)
