# Proving that exactly half the partitions of $n$ into powers of 2 have an even number of parts

Could you help me how to prove that exactly half the partitions of $n$ into powers of 2 have an even number of parts, please?

Let's go with a generating function proof since you're into those!

Consider the product

$$P=\prod_{n=0}^\infty\sum_{j=0}^\infty x^{2^nj}.$$

The coefficient of $x^m$ in this product is the number of partitions of $m$ into powers of two. If we modify it slightly by writing

$$P=\prod_{n=0}^\infty\sum_{j=0}^\infty (-1)^jx^{2^nj},$$

then each partition is given the weight $\pm 1$ according to whether the number of its parts is odd or even. Now of course this product is simply

$$P=\prod_{n=1}^\infty(1+x^{2^n})^{-1},$$

which, by my solution to your other problem, is equal to $1-x$. Thus for $m=0$ and $m=1$, there are respectively $1$ more and $1$ less partitions of $m$ into an even number of parts as there are into an odd number of parts; for all other $m$, there are equally many.

• I'm not understanding the application, for example, if we take $n=6$ and the partition $2,4$ then if we add together these two elements we have 6 but this isn't a power of two. – Mec Nov 11 '11 at 5:30
• You're absolutely right, thank you. I actually had the correct solution at first, but then I wrote a bunch of nonsense instead. It works now! – Bruno Joyal Nov 11 '11 at 5:36
• I'm not sure this is a bijection. Take $n=7$ and the partition 1,2,4 then this isn't the image of a partition in two parts thru your application – Mec Nov 11 '11 at 5:39
• Sorry for this. I shouldn't post when I'm so tired. Here's something you might like better (if only because it works ;)). – Bruno Joyal Nov 11 '11 at 5:47

Let $S_e$ be the set of even partitions and $S_o$ the set of odd. Take any partition $s$ of $S_e$.

Let $2^r$ be the highest power of $2$ in $s$. If $s$ contains a single $2^r$ write $s = 2^r + p$ for remainder partition $p$ and define $s' = 2^{r-1} + 2^{r-1} + p$ noting that the resulting odd partition contains more than one of it's highest power of $2$, being $2^{r-1}$.

Similarly, if $s$ contains multiple $2^r$ then write $s' = 2^{r+1} + p$, noting that the resulting odd partition contains only one of it's highest power $2$, being $2^{r+1}$. This defines a bijection.