Thread by @pgeerkens

@GWOMaths @MathsTim Lemma 1:
From every distinct partition of n an odd partition of n can be uniquely associated.

@GWOMaths @MathsTim Proof:
For the integer n, any distinct partition can be written as

SUM_i(Gi . 2^Ki)

where every Gi is odd and Ki >= 0

because every positive integer is uniquely expressable as an odd positive integer times a power of 2.

@GWOMaths @MathsTim By grouping on each distinct value of the Gi we get a uniquely associated odd partition of n
Q.E.D.

Lemma 2:
From every odd partition of n a distinct partition of n can be uniquely associated.

@GWOMaths @MathsTim Proof:
For the integer n, any odd partition can be written as the sum over i of terms

Ci . Gi

where every Gi is odd and Ci is the occurrence frequency of that Gi.

@GWOMaths @MathsTim But every Ci can in turn be written uniquely as the sum over j of

Dj,i . 2^j

where every Dj,i is either 0 or 1 and 0 <= j <= J where J is the smallest integer such that 2^J >= n.

@GWOMaths @MathsTim Thus our partition is (uniquely) expressable as

SUM_i( SUM_j(Dj,i . 2^j) . Gi)

which is a distinct partition of n.
Q.E.D.

@GWOMaths @MathsTim Lemma 3:
The number of distinct partitions of n equals the number of odd partitions of n.

Proof:
Lemmas 1 and 2 define a bijection between the odd and distinct partitions of n.
Q.E.D.

Therefore g(n) / f(n) = 1.

@GWOMaths @MathsTim @threadreaderapp unroll