# Generating function and formula for the number of compositions of $n$ into $k$ parts, each of which is odd.

Find the generating function for the number of compositions of $$n$$ into $$k$$ parts, each of which is odd. Apply algebraic manipulation and the formal power series expansion of some basic functions to find a formula for the coefficient of $$x^n$$ in the generating function.

I have that the generating function for the number of compositions comes from $$(x+x^3+x^5+...)^k=\bigg(\frac{x}{(1-x^2)}\bigg)^k=x^k\sum_{n=0}^\infty\begin{pmatrix}n+k-1\\k-1\end{pmatrix}x^{2n}$$ and I think that the formula I want to get too eventually is $$\begin{cases} 0,&\text{if }n-k\text{ is odd}\\\\ \dbinom{\frac{n+k}2-1}{\frac{n-k}2},&\text{if }n-k\text{ is even}\;. \end{cases}$$ I'm not sure how to get from the first formula to the second, any help would be appreciated!

• In the first formula, where did the sum over $n$ come from? You're summing an expression for $n$ to infinity that doesn't depend on $n$, so this series diverges. – joriki Dec 8 '19 at 21:11

You are happy that the generating fuction is $$\begin{eqnarray*} \sum_{N=0}^{\infty} \binom{N+k-1}{k-1} x^{2N+k} \text{ ?} \end{eqnarray*}$$ This means there are $$\binom{N+k-1}{k-1}$$ compositions (into $$k$$ odd parts) of $$n$$ where $$n=2N+k$$. So $$n-k$$ needs to be even (& the number of ways will be zero if it is odd) ... A little bit of algebra will lead to the conclusion you require.