# A question about integer partitions

Lets say that $$p(n)$$ is the number of ways of partitioning $$n$$ into integers (order doesn't matter).

How does one prove that $$p(n) \equiv p(n|\text{distinct odd parts}) \mod 2$$?

For $$n=1$$, there's only one partition with one part, $$1$$. And this is also a partition into distinct odd parts.

For $$n=2$$, there are $$2$$ partitions and $$0$$ partitions into distinct odd parts.

For $$n=3$$, there are $$3$$ partitions and $$1$$ partition into distinct odd parts (partition into a single part $$3$$)

For $$n=4$$, there are $$5$$ partitions and $$1$$ partition into distinct odd parts ($$3+1$$)

and so on. This seems to hold for small $$n$$, I calculated it by hand.

I don't really know how to prove this though. One thing one might prove is that $$p(n|\text{odd parts with at least one part occurring twice})+p(n|\text{at least one even part}) \equiv 0\mod2$$

But I don't know how to prove that either. I'm looking for a solution that doesn't invoke generating functions, but a solution with generating functions is welcome. Any help is very appreciated, thanks!

Here the lazy person approach: the number of partitions is given by $$p(n) = [x^n]\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}$$ while the number of partitions into distinct odd parts is given by $$p_1(n) = [x^n](1+x)(1+x^3)(1+x^5)\cdots$$ so we just need to prove that all the coefficients of $$(1-x)(1-x^2)(1-x^3)\cdots(1+x)(1+x^3)(1+x^5)\cdots$$ except the very first one are even. On the other hand in $$\mathbb{F}_2[[x]]$$ we have $$\prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=\prod_{n\geq 1}(1-x^{2n})\prod_{m\geq 0}(1+x^{4m+2})=\prod_{n\geq 1}(1-x^{4n})\prod_{m\geq 0}(1+x^{8m+4})$$ since $$(1-x^{2n+1})(1+x^{2n+1})=(1-x^{4n+2})=(1+x^{4n+2})$$ and so on. By induction $$\prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=\prod_{n\geq 1}(1-x^{2^k n})\prod_{m\geq 0}(1+x^{2^{k+1}m+2^k})$$ for any $$k\in\mathbb{N}$$. It follows that in $$\mathbb{F}_2[[x]]$$ both series equal $$1$$, so $$p(n)$$ and $$p_1(n)$$ always have the same parity.
By playing a bit with the Jacobi triple product we also have $$\prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=1+2\sum_{d\geq 1}(-1)^d x^{2d^2}.$$
The number of partitions of $$n$$ into distinct odd parts equals the number of self-conjugate partitions of $$n$$. The number of non-self-conjugate partitions of $$n$$ is even.