[2.4] Exercise 7
Let \(\lfloor x \rfloor\) denote the largest integer smaller than or equal to \(x\). Use Theorem 1 to prove that \(\lfloor n/3 \rfloor + 1\) is the number of partitions of \(n\) into distinct parts where each part is either a power of two or three times a power of two.
Proof
Let \(N = \{1,3\}\). Then by Theorem \(1\), \((N,M)\) is an Euler pair where \(M\) consists of parts that are either a power of two or \(3\) times a power of \(2\). So
$$
\begin{align}
M = \{1,2,4,8,16,32,\cdots\} \cup \{3,6,12,24,48,\cdots\}
\end{align}
$$
Moreover,
$$
\begin{align}
p(n \mid \text{parts in } N) = p(n \mid \text{distinct parts in } M) \quad\quad\quad (1)
\end{align}
$$
Then consider \(n\). The number of partitions of \(n\) using parts of \(N\) is the number of ways to write \(n\) as a sum of \(3\)’s and \(1\)s:
$$
\begin{align}
n = 3 + 3 + 3 + \cdots + 3 + 1 + 1 + \cdots + 1
\end{align}
$$
Let \(j\) be the number of \(3's\) used in the sum. Then
$$
\begin{align}
n = 3j + (n - 3j) \cdot 1
\end{align}
$$
This is true if \(n - 3j \geq 0\). This means that
$$
\begin{align}
0 \leq j \leq n/3
\end{align}
$$
where for each \(j\) we have exactly one partition. So \(j\) can take the values
$$
\begin{align}
j = 0,1,2,3,\cdots, \lfloor n/3 \rfloor
\end{align}
$$
Hence
$$
\begin{align}
p(n \mid \text{parts in } N) = \lfloor n/3 \rfloor + 1
\end{align}
$$
Using \((1)\)
$$
\begin{align}
p(n \mid \text{distinct parts in } M) = \lfloor n/3 \rfloor + 1
\end{align}
$$