Let $n \geq 2$. Show that the number of compositions of $n$ with an even number of parts is equal to the number of compositions of $n$ with an odd number of parts.
I am trying to take the difference with the two generating series but I am kind of stumped.
Best Answer
Take an integer $n\ge 2$, and write down $n$ consecutive $1$'s, with a little space between them, like this: $$1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1$$ A composition of $n$ into $k$ parts is obtained by choosing $k-1$ of the $n-1$ "gaps" between consecutive $1$'s to insert a separator into. For example, the composition $10=2+5+3$ is represented by $$1\quad1\,\ast\,1\quad1\quad1\quad1\quad1\,\ast\,1\quad1\quad1$$
There are $\binom{n-1}{k-1}$ ways to choose $k-1$ gaps. So there are $\binom{n-1}{k-1}$ compositions of $n$ into $k$ parts.
The number of compositions of $n$ into an even number of parts is the sum of all $\binom{n-1}{k-1}$ where $k$ is even, that is, $k-1$ is odd.
The number of compositions of $n$ into an odd number of parts is the sum of all $\binom{n-1}{k-1}$ where $k$ is odd, that is, where $k-1$ is even.
It is a standard theorem that the sum of the binomial coefficients $\binom{m}{i}$ where $i$ ranges over the even integers is the same as the sum where $i$ ranges over the odd integers. There are many proofs. The easiest may be by considering the binomial expansion of $(1+(-1))^m$.