<s>[INST] How many compositions of n are there with same parity Let n be a non-negative integer. How many compositions of n are there where the i-th part has the same parity as i? For example, compositions of 7 that satisfy this condition are (7), (5,2), (3,4), (1,6), (1,2,1,2,1). Express your answer as the coefficient of a simplified rational expression.
can someone help me please :(
 [/INST] Hint: The number of solutions where there is exactly 1 part is the coefficient of $x^n$ in $x + x^3 + x^5 + \ldots  = \frac{x}{1-x^2}$.
Hint: The number of solutions where there are exactly 2 parts is the coefficients of $x^n$ in $(x+x^3+x^5 + \ldots ) \times (x^2 + x^4 + x^6 + \ldots )  = \frac{ x } { 1-x^2} \times \frac{x^2} { 1-x^2} $.
Hence, the number of solutions is (summing over all possible number of parts) is the coefficient of $x^n$ in
$$ \sum_{i=1}^\infty \left(\frac{x}{1-x^2} + \frac{ x } { 1-x^2} \times \frac{x^2} { 1-x^2} \right) \left(\frac{ x } { 1-x^2} \times \frac{x^2} { 1-x^2} \right)^i $$
Simplify this further.
</s>