Can you help me with this?

One of these has 5 parts, 4 of them have 4 parts, 6 of them have 3 parts, 4 of them have 2 parts, and one of them has one part. In total, there are 1+4+6+4+1 = 16 compositions of 5. We discussed these things in Zoomtime, you might one rewatch starting from minute 36 of the cloud recording for November 2 before you attempt these problems! 1. Prove that the number of composition of n with 7' parts is (:3). (It is ne to repeat the proof I explained in the lecture for this!) 2. Use the result from Q1 to prove that the total number of compositions of n is 2\"\". {You probably want to refer to the binomial theorem here.) 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