Let S be the set of binary strings consisting of a (nonempty) block of Os followed by a (nonempty) block of 1s, such that if the block of Os has odd length, then the block of 1s has even length. Let an be the number of strings of length n in S. (a) Find ao, a1, a2, a3. (b) Prove that S = {0}{0}*{1}{1}* \ {0}{00}*{1}{11}*. (c) Show that the generating function for S is x (2+x) s(x) = (1-x)2 (d) Write down a recurrence equation for an. Determine a closed formula for an for all n, and find a1001.