Question 37
Let $P(n)$ be the number of ways of partitioning a positive integer $n$ as a sum of powers of $2$, where the order of summands is not important. For example, $P(5) = 4$, since $5 = 4+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1$. Prove that for each positive integer $n$ the following identity holds:
$$
P(n) + (-1)^{a_1}P(n-1) + (-1)^{a_2}P(n-2) + \dots + (-1)^{a_{n-1}}P(1) + (-1)^{a_n} = 0,
$$
where $a_k$ is the number of ones in the binary notation of $k$.
$$
P(n) + (-1)^{a_1}P(n-1) + (-1)^{a_2}P(n-2) + \dots + (-1)^{a_{n-1}}P(1) + (-1)^{a_n} = 0,
$$
where $a_k$ is the number of ones in the binary notation of $k$.