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?
Proving that exactly half the partitions of $n$ into powers of 2 have an even number of parts
2 Answers
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.
-
0Sorry for this. I shouldn't post when I'm so tired. Here's something you might like better (if only because it works ;)). – 2011-11-11
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.