Puzzling Partitions

It turns out that $D(n) = O(n)$ for all $n \in \mathbb{N}$ !

I saw a wonderful proof of this using generating functions that I'll re-interpret here.

---

Let's prove this surprising result using generating functions!

Let

$o(x) = o_1 + o_2x^2 + o_3x^3 + ... + o_nx^n+ ...$

where we define $o_n$ to be $O(n)$ .

Similarly we let

$d(x) = d_1 + d_2x^2 + d_3x^3 + ... + d_nx^n+ ...$

where we define $d_n$ to be $D(n)$ .

We'll reinterpret these two power series.

---

We must have

$o(x) = (1+x+x^2 + x^3 + x^4 +...)(1+x^3+x^6+x^9+x^{12}+...)(1 + x^5 + x^{10} + x^{15}...) ...$

since we can create the bijection between expanding out these brackets term by term and by choosing how many of each odd integer we choose to sum.

To see this we can think of each term in the the first bracket $(1+x+x^2 + x^3 + x^4 +...)$ as representing how many $1$ s we put into a given summation and similarly $(1+x^3+x^6+x^9+x^{12}+...)$ as how many $3$ s we put into a given summation. For example the sum $5 = 1 + 1 + 3$ corresponds to picking $x^2$ out of the first bracket and $x^3$ out of the second.

Since the exponents will sum when we multiply the terms in the expansion we see that $x^n$ must occur exactly the same amount of ways we can sum $n$ using odd numbers!

---

Now let's look at $d(x)$ in another way!

$d(x) = (1+x)(1+x^2)(1+x^3)...(1+x^n)...$

I won't fill in the details here of why this is true but hopefully with a little thought of how we re-interpreted $o(x)$ we can see why this is true.

---

But now we see that

\begin{aligned} d(x) &= (1+x)(1+x^2)(1+x^3)...(1+x^n)...\\ &\text{but since \$x^{2m}-1 = (x^m-1)(x^m+1) \implies(x^m+1) = \frac{x^{2m} - 1}{x^m-1}\$ we have}\\ &= \frac{x^2-1}{x-1} \frac{x^4-1}{x^2-1} \frac{x^6-1}{x^3-1} ...\\ &\text{cancelling out even powered terms gives us }\\ &= \frac{\color{#D61F06}{x^2-1}}{x-1} \frac{\color{#3D99F6}{x^4-1}}{\color{#D61F06}{x^2-1}} \frac{\color{#20A900}{x^6-1}}{x^3-1}\frac{\color{#69047E}{x^8-1} }{\color{#3D99F6}{x^4-1}}...\\ &=\frac{1}{1-x} \frac{1}{1-x^3} \frac{1}{1-x^5} ... \\ &= o(x) \end{aligned}

So they are equal and hence their co-coefficients are respectively equal.

So $O(n) = D(n)$ for all $n \in \mathbb{N}$ therefore $O(2016) = D(2016)$ .