Number of partitions of $n$ into distinct even parts.

Question

Question from my last exam:

Let $r_n$ denote the number of partitions of $n$ into distinct parts. Prove that $$ \sum_{i=0}^n(-1)^i r_i r_{n-i} $$ is the number of partitions of $n$ into distinct even parts.

For odd $n$, the sum has an even number of parts and each of them has a pair with the opposite sign. The signs will be opposite because at the beginning with the first element on the left there will be a plus, with the first element on the right there will be a minus. Then we can remove these elements and the signs will reverse. In this way, for odd $n$, the sum is $0$.

That was the easy part. How can this be shown for even $n$?

Thanks.

Answer 1

Let \begin{align*} \color{blue}{R(z)=\sum_{n=0}^{\infty}r_nz^n=\prod_{m=1}^{\infty}\left(1+z^m\right)}\tag{1} \end{align*} be the generating function with $r_n$ giving the number of partitions of $n$ into distinct parts. The representation by the product (1) is clear, since each factor represents either no contribution at all or one and only one part of size $m$.

Since \begin{align*} R(z)R(-z)&=\left(\sum_{k=0}^{\infty}r_kz^k\right)\left(\sum_{l=0}^{\infty}(-1)^lr_lz^l\right)\\ &=\sum_{n=0}^{\infty}\left(\sum_{{k+l=n}\atop{k,l\geq 0}}(-1)^lr_kr_{l}\right)z^n\\ &=\sum_{n=0}^{\infty}\left(\color{blue}{\sum_{k=0}^n (-1)^kr_kr_{n-k}}\right)z^n \end{align*}

we want to show \begin{align*} \color{blue}{R(z)R(-z)=\prod_{m=1}^{\infty}\left(1+z^{2m}\right)}\tag{2} \end{align*}

We start with the left-hand side of (2) and we obtain from (1): \begin{align*} \color{blue}{R(z)R(-z)}&=\prod_{m=1}^{\infty}\left(1+z^m\right)\prod_{m=1}^{\infty}\left(1+(-z)^m\right)\\ &=\prod_{m=1}^{\infty}\left(\left(1+z^m\right)\left(1+(-1)^mz^m\right)\right)\\ &=\prod_{m=1}^{\infty}\left(1+z^m+(-z)^m+(-1)^mz^{2m}\right)\\ &=\prod_{m=1}^{\infty}\left(1+2z^{2m}+z^{4m}\right) \prod_{m=1}^{\infty}\left(1+z^{2m-1}-z^{2m-1}-z^{4m-2}\right)\tag{3}\\ &\,\,\color{blue}{=\prod_{m=1}^{\infty}\left(\left(1+z^{2m}\right)^2\left(1-z^{4m-2}\right)\right)}\tag{4}\\ \end{align*} In (3) we split the product into products respecting even and odd parts separately.

We can also write the product (1) as \begin{align*} \color{blue}{R(z)}&=\prod_{m=1}^{\infty}\left(1+z^m\right)=\prod_{m=1}^{\infty}\frac{1-z^{2m}}{1-z^m}\\ &=\prod_{{m=1}\atop{m\ \mathrm{ odd}}}^{\infty}\frac{1}{1-z^m}\\ &\,\,\color{blue}{=\prod_{m=1}^{\infty}\frac{1}{1-z^{2m-1}}}\tag{5} \end{align*} showing that the number of partitions of $n$ into distinct parts is the same as the number of partitions of $n$ into odd parts.

Thanks to (5) we can now continue with (4). We obtain \begin{align*} \color{blue}{R(z)R(-z)}&=\prod_{m=1}^{\infty}\left(\left(1+z^{2m}\right)^2\left(1-z^{4m-2}\right)\right)\\ &=\prod_{m=1}^{\infty}\left(1+z^{2m}\right)\prod_{m=1}^{\infty}\frac{1}{1-z^{4m-2}} \prod_{m=1}^{\infty}\left(1-z^{4m-2}\right)\tag{$\to $(5)}\\ &\,\,\color{blue}{=\prod_{m=1}^{\infty}\left(1+z^{2m}\right)} \end{align*} and the claim (2) follows.