This is the question:

Question 5. Let a\" he the number of even sized subsets of {1, . . . n}. (You already know what this is, but pretend that you don't.) Use Theorem 8.21 from the hook to determine the exponential generating function for an. The calculation here is somewhat simple, but the purpose of the exercise to ex plain how you are using the theorem and why it applies. This explanation is what will be graded. Of course your answer will give an explicit formula for an. Hint: You might need to know the Maelanrin series for oosh(x). Theorem 8.21 (Product formula, exponential version). Let an be the number of ways to build a certain structure on an n-etement set, and tet b\" be the number of way to buitd another structure on an n-eternent set. Let en, be the number of ways to separate [n] into the disjoint subsets S and T, ['5' U T = [11]), and then to build a structure of the rst kind on 5', and a structure of the second kind on T. Let 14(3), 3(3), and C(33) be the respective erponentiat generating.I functions of the sequences {an}, {bn}, and {on}. Then A(I)B($] 2 C(33). A Function [3 Worth Many Numbers. Generating Functions 183 Note that while Theorems 3.5 and 8.21 sound very similar, they apply in different circumstances. Theorem 8.5 applies when [n] is split into two parts so that one part is [i]. That is, [n] is split into internals. Theorem 8.21 applies when [n] is split into two parts with no restrictions. In other words, the rst theorem applies when our objects are linearly ordered [like days in a calendar, or people in a line), and we cut that linear order somewhere to get two subsets. The second theorem applies when we are free to choose our two subsets, that is, they do not have to be consecutive objects in a previously ordered line. Proof. (of Theorem 8.21) If 3 has i elements, then there are (:1) ways to choose the elements of 3. Then there are a,- ways to build a structure of the rst kind on S, and bn_,; ways to build a structure of the second kind on T, and this is true for all i, as long as D E i E n. Therefore, c,, = 2:12,] (1:) a,b,,_,-, and our claim follows from Lemma 8.20. CI