PLEASE HELP

Math 231 Homework #7 The problems on this homework are all to do with compositions. By def- inition, a composition of n, is a sequence (n.1, . . .,n.r) of positive integers summing to 11, i.e., n = 111 + - - - + or. The number 1' here is the number of ports in the composition. For example, here are the compositions of 5: (1,1,1,1,1); (1,1,1,2),(1,1,2,1), (1,2,1,1),(2,1,1,1); (1, 1,3), (1,3, 1), (3, 1, 1), (2,2, 1), (2, 1, 2), (1,2,2); (114},{411}1{2:3}1(312); (5)- 3. For n 2 1, let Xn be the set of all compositions of n. (a) Prove that |Xntil = 1+ |Xil + . . . + |Xml. (b) Use the result from (a) and Mathematical Induction to prove that (Xn| = 2"-1. This gives another approach to question 2! 4. Let Yn be the set of compositions of n all of whose parts are equal to 1 or 2. For example, Yi = {(1) } and Y2 = {(1, 1), (2)}. Let Y, be the subset of Y, consisting of all of the elements of Y, whose last part is 1. Let Y," be the subset of Y, consisting of all of the elements of Y, whose last part is 2. Show: (a) |Yal = 1YRI + 1Y,"'1. (b) [Yl = 1Ym-1/ and [Y,"| = [Yn-21. (c) Recall the Fibonacci sequence (fn)n21 is defined recursively by f1 = f2 = 1 and fn+1 = fn + fn-1. Use (a), (b) and Mathematical Induction to prove that | Ym| = fn+1 for n > 1