Partition of Integer into Powers of 2 for Consecutive Integers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $\map b n$ denote the number of ways $n$ can be partitioned into (integer) powers of $2$.


Then:

$\map b {2 n} = \map b {2 n + 1}$


Proof

We prove the theorem by establishing a bijection between the set of partitions of $2 n$ with that of $2 n + 1$, under the constraint where each partition is an integer power of $2$.


We have that $2^k$ is even for all $k > 0$.

Also, we have that $2 n + 1$ is odd for all $n$.

So, for each partition of $2 n + 1$ into integer powers of $2$, there is at least one part of size $1$.

Removing this part gives a partition of $2 n$ into integer powers of $2$.


The inverse of this is adding a part of size $1$ to a partition of $2 n$.

This will give a partition of $2 n + 1$ into integer powers of $2$.

Hence both removing and adding are well-defined mappings.

Thus they are bijections.


Therefore:

$\map b {2 n} = \map b {2 n + 1}$

$\blacksquare$


Sources