Counting set for generating functions

Question

Give a proof of the following identity by counting two sets of partitions in two different ways.

\begin{equation*} \prod_{i\geq 0}(1+x^{2i+1})=1 + \sum_{n\geq 1}x^{n^2}\prod_{j=1}^n\frac{1}{1-x^{2j}} \end{equation*} To prove this inductively, i only successfully complete the base cases, however the counting set for the left side i concluded that would be the number of partitions of n with distinct odd parts and for RS the product part would be the number of partitions of n with even parts, how would the summation of $x^{n^2}$ come into play with counting set. How would i initiate my proof?

Answer 1

Minor notational note: If you are going to start the sum on the right with $n=0$, then you don't need the explicit term $1$, as long as you adopt the convention that empty products equal $1$.

You can think in terms of Ferrers diagrams. Recall that $n^2=1+3+5+\ldots+(2n-1)$. So, for example, a partition of $3^2$ is

ooooo
ooo
o

and a partition of $4^2$ is

ooooooo
ooooo
ooo
o

Now you need to show that any partition consisting of $n$ distinct odd parts can be obtained by "gluing" the diagram similar to those above for the partition of $n^2$ to a diagram for a partition consisting of at most $n$ even parts.

As an example, here's a partition of $28$ into $n=4$ distinct odd parts. Separating out the partition of $16=4^2$ into four distinct odd parts leaves a partition of $12$ into at most four (in this case three) even parts:

ooooooooooooooo          ooooooo oooooooo         ooooooo        oooooooo
ooooooo            =     ooooo oo            =    ooooo     +    oo
ooooo                    ooo oo                   ooo            oo
o                        o                        o

The coefficient of $x^k$ in the product on the right side manifestly counts partitions of $k$ into even parts of size at most $2n$. You need to prove that it also counts partitions of $k$ into at most $n$ even parts.

As a hint for this part, consider the partition of $12$ into at most four even parts from the previous example. By pairing adjacent columns of the diagram, combining paired columns into single columns of twice the length, and then transposing, we get a partition of $12$ into even parts of size at most $8$.

                                        oooo
oooooooo           oo oo oo oo          oooo               oooooo
oo          <-->   oo            <-->   o        <-->      oo
oo                 oo                   o                  oo
                                        o                  oo
                                        o

Finally, combining the product with $x^{n^2}$ and summing over the number of distinct odd parts, $n$, gives the result.

Answer 2

Hint: For how to show the formula algebraically.

Expand the product, multiplying all the $1$'s together gives $1$. Now pick all the terms with exactly $1$ $x^{2i+1}$ term gives \begin{eqnarray*} \sum_{i=0}^{\infty} x^{2i+1}=?. \end{eqnarray*} Now pick all the terms with exactly $2$ $x^{2i+1}$ terms, this gives \begin{eqnarray*} \sum_{i_1=0}^{\infty} \sum_{i_2=i_1+1}^{\infty} x^{2i_1+2i_2+2}=?. \end{eqnarray*} $\vdots$

Now pick all the terms with exactly $k$ $x^{2i+1}$ terms,this gives \begin{eqnarray*} \sum_{i_1=0}^{\infty} \sum_{i_2=i_1+1}^{\infty} \cdots \sum_{i_k=i_{k-1}+1}^{\infty} x^{2i_1+2i_2+\cdots+2i_k+k}=?. \end{eqnarray*}