Q1 (10 points) In Assignment 3 Question 4, we dened 0,, to be the set of all integer compositions ofn with odd number of parts, and each part is congruent to 1 modulo 3. We proved that |Cn| = [22\"] . You can derive the following recurrence for any n 2 6: lcnl : ICE2| + 2'0113|_|Cn6| Give a combinatorial proof of this identity for any n 2 6 where n, i 1 (mod 3). You need to mention where the condition in i 1 (mod 3) is needed in your proof, or you can prove this identity for all n 2 6. Hint: One way to do this is to consider the following three (not-necessarily-disjoint) sets, and use bijections. (i) X\" is the set of all compositions in C\" where the rst two parts are both 1's. {ii} Y\" is the set of all compositions in 0,; where the rst part is at least4. (iii) Zn is the set of all compositions in 0'...I where the second part is at least 4