Question 9: A 11-free bitstring is a bitstring that does not contain the substring 11. Let Bn be the number of 11-free bitstrings of length n. Observe that by symmetry this is the same as the number of 00-free bitstrings of length n, which we computed in class. A 011-free bitstring is a bitstring that does not contain the substring 011. Let S, be the number of 011-free bitstrings of length n. In this question we will compute S,. (a) Find S, and S2. (b) Let S be a 011-free bitstring of length n. Prove that any substring of S that starts with a 0 must be 11-free. (c) Find a recursive expression for S, for n 2 3. Hint: part of your expression should include the number of 11-free bitstrings. (d) Prove that Et-, Bi = Bn+2 - 3. (e) Prove that Sn = fn+3 - 1, where fn+3 is the n + 3"d fibonacci number