Question 4. 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) (b) Find ao, ai, a2, a3. Prove that S-10Ho (c) Show that the generating function for S is 3 (2+x) d) Write down a recurrence equation for an (e) Determine a closed formula for an for all n, and find a1001 Question 4. 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) (b) Find ao, ai, a2, a3. Prove that S-10Ho (c) Show that the generating function for S is 3 (2+x) d) Write down a recurrence equation for an (e) Determine a closed formula for an for all n, and find a1001