SILK-ROAD 2016 Problem 4

Let $P(n)$ be the number of ways to split a natural number $n$ to the sum of powers of two, when the order does not matter. For example $P(5) = 4$ , as $5=4+1=2+2+1=2+1+1+1=1+1+1+1+1$ . Prove that for any natural the identity $P(n) + (-1)^{a_1} P(n-1) + (-1)^{a_2} P(n-2) + \ldots + (-1)^{a_{n-1}} P(1) + (-1)^{a_n} = 0,$ is true, where $a_k$ is the number of units in the binary number record $k$ .

source