Saudi Arabian IMO Booklet

Let $D(n)=E(n)-O(n)$. We trivially have $O(1)=1$ and $E(1)=0$, thus $D(1)=-1$, and $E(2)=O(2)=1$ (respectively $2=1+1$ and $2=2$), hence $D(2)=0$. We will show by total induction that $D(n)=0$ for all $n>2$. Assume it holds for all numbers from $2$ to $n-1$. If $n$ is odd, a partition must contain at least one $1$. Since the addition of $1$ changes the parity of the number of one's it follows that $E(n)=O(n-1)$ and $O(n)=E(n-1)$, hence since $D(n)=-D(n-1)=0$. If $n$ is even the partition must contain an even number $2k$ of $1$s. If it contains $2k=n$ or $2k=n-2$, then we have the unique solutions $$1+1+\cdots +1\text{ and }2+1+1+\cdots +1,$$ the first adding to $E(n)$, the second to $O(n)$. For other, smaller, values of $k$ we note that the remaining exponents are all even, and we can thus apply the inductive hypothesis to $\frac{n-2k}{2}$. Thus, it follows that for even $n$ we will also have $D(n)=0$. This completes the proof. $\square$

---

Alternative solution.

Let $G(x)=1+{\sum }_{i=1}^{\infty }D(i)x^i$ be the generating function for the sequence we desire. To count partitions with an odd number of odd-appearing exponents as negative, we will multiply those choices as negative. Thus, we have that $$G(x)=(1-x+x^2-x^3+x^4-\dots )(1-x^2+x^4-x^6+x^8-\dots )(1-x^4+x^8-x^{12}+x^{16}-\dots )\dots ,$$ where the $i$-term corresponds to choosing the number of times $2^{i-1}$ is represented in the partition. Taking the expression for each power series, one now finds $$G(x)=\frac{1}{1+x}\frac{1}{1+x^2}\frac{1}{1+x^4}\frac{1}{1+x^8}\dots$$ However, $$\begin{array}{rl}\frac{G(x)}{1-x}& =\frac{1}{1-x}\frac{1}{1+x}\frac{1}{1+x^2}\cdots =\frac{1}{1-x^2}\frac{1}{1+x^2}\frac{1}{1+x^4}\cdots \\ & =\frac{1}{1-x^4}\frac{1}{1+x^4}\frac{1}{1+x^8}\cdots =\cdots =1.\end{array}$$ Thus, $G(x)=1-x$ from which it follows that $D(1)=-1$ and $D(n)=0$ for all $n>1$. $\square$