Proving that odd partitions and distinct partitions are equal

Question

I am working through The Theory of Partitions by George Andrews (I have the first paperback edition, published in 1998).

Corollary 1.2 is a standard result that shows that the number of partitions of $n$ into odd parts is the same as the number of partitions of $n$ into distinct parts.

Andrews's proof uses generating functions, but it contains this step that has me confounded:

$$ \prod_{n = 1}^\infty \frac{1 - q^{2 n }}{1 - q^n} = \prod_{n = 1}^\infty \frac{1}{1 - q^{2 n - 1}}. $$

Can anybody point me in the right direction? I tried turning $1 - q^n$ into an infinite sum and then expanding, to get $$ \frac{1 - q^{2 n }}{1 - q^n} = 1 + q + q^2 + \dots + q^{2 n -1}, $$ but I don't see how this manipulation will help me.

Answer 1

See if this helps?

\begin{align*} \prod_{n = 1}^\infty \frac{1 - q^{2 n }}{1 - q^n} &= \frac{1 - q^{2}}{1 - q}\cdot\frac{1 - q^{4 }}{1 - q^2}\cdot\frac{1 - q^{6 }}{1 - q^3}\cdot\dots\\ &= \left[\frac{1}{1-q}\cdot\frac{1}{1-q^3}\cdot\frac{1}{1-q^5}\dots\right]\left[\frac{1 - q^{2}}{1 - q^2}\cdot\frac{1 - q^{4 }}{1 - q^4}\cdot\frac{1 - q^{6 }}{1 - q^6}\cdot\dots\right]\\ &= \left[\frac{1}{1-q}\cdot\frac{1}{1-q^3}\cdot\frac{1}{1-q^5}\dots\right]\left[1\right]\\ &= \prod_{n = 1}^\infty \frac{1}{1 - q^{2 n - 1}}\\ \end{align*}

Where the second step indicates a rearrangement of the terms. Now one must be careful in infinite rearrangements - you should check for the absolute convergence of an infinite sum. see here You should check this for validity of the second step.

Answer 2

$$\prod_{n=1}^\infty \frac{1}{1 - q^n} = \prod_{n=1}^\infty \frac{1}{(1-q^{2n-1})(1-q^{2n})}$$

Answer 3

Who needs generating functions? We can set up a correspondence between distinct partitions and odd partitions by means of two inverse procedures, which I call doubling and halving.

Given an odd partition

$13=3+3+3+1+1+1+1$

we double identical pairs -- $1+1\to 2, 3+3\to6$. Note that one of the $3$'s remains unpaired because we had an odd number of them:

$13=6+3+2+2$

And then we double again with the remaining identical pair of $2$'s, which leaves us ultimately with only single numbers thus a distinct partition into which the odd partition is mapped:

$13=6+4+3$

Now go the other way. Start with a distinct partition such as

$13=6+4+3$

and split each even number in half, iterating until only odd numbers are left:

$13=3+3+2+2+3=3+3+3+2+2$

$13=3+3+3+1+1+1+1$

Thus doubling uniquely maps $3+3+3+1+1+1+1$ into $6+4+3$ and halving uniquely maps $6+4+3$ back into $3+3+3+1+1+1+1$.

What's really happening?

Bit by bit

Let's look closely at the evolution of the $3$'s from the odd partition. In binary arithmetic there are $11_2$ of these. Doubling therefore inevitably leads to one term equal to $2×3$, from the first $1$ bit, plus $1×3$ from the second $1$ bit. Thus in base ten, $3+3+3\to6+3$. And if we start from a distinct partition with $6+3$ where $6$ and $3$ are the only numbers with $3$ as the largest odd factor, halving is sure to give $11_2$ threes or $3+3+3$.

We can see the same thing with the $1$'s. The odd partitions started with $100_2$ of these terms, so repeatedly doubling can't leave any terms of $1×1$ or $2×1$. We can only get a term of $4×1$ from the $1$ bit in $100_2$, and going the other way $4$ which is $1×2^2$ can generate a string of $1$'s that is $100_2$ or four terms long.

Similar correspondences hold in general connecting each odd partitions uniquely with a distinct one. Let's look at all of them for $13$:

$13\to13$*

$11+1+1\to11+2$

$9+3+1\to9+3+1$

$9+1+1+1+1\to9+4$

$7+5+1\to7+5+1$

$7+3+3\to7+6$

$7+3+1+1+1\to7+3+2+1$

$7+1+1+1+1+1+1\to7+4+2$

$5+5+3\to10+3$

$5+5+1+1+1\to10+2+1$

$5+3+3+1+1\to6+5+2$

$5+3+1+1+1+1+1\to5+4+3+1$

$5+1+...+1\to8+5$

$3+3+3+3+1\to12+1$

$3+3+3+1+1+1+1\to6+4+3$

$3+3+1+...+1\to6+4+2+1$

$3+1+...+1\to8+3+2$

$1+...+1\to8+4+1$#

*A partition that is both distinct and odd maps into itself.

#An odd partition of all $1$'s maps into the binary representation of the number, which dovetails with the arguments above.