Nice generating function problem! (Note: In above, "number of units in the binary record of $k$" just means sum of digits of $k$ when expressed in binary) Notice that $P(n) = P(n-1)$ if $n$ is odd and $P(n) = P(n-1) + P(\frac{n}{2})$ if $n$ is even, which can easily be seen by casework on whether one of the powers of $2$ is $2^0 = 1$. Therefore, this implies that the generating function $F(x) = \sum_{i = 1}^{\infty} P(i)x^i$ satisfies the recursion $F(x^2) + xF(x) = F(x) - x,$ i.e. $F(x^2) = (1-x)F(x) -x$. Now, consider the generating function $Q(x) = \sum_{i = 0}^{\infty} (-1)^{a_i} x^i,$ where we let $a_0 = 0$ by convention. Observe that for the problem at hand, it would suffice to show that $(1+F(x)) (Q(x)) = 1,$ as then the problem would follow by considering the $x^n-$coefficient of both sides. Letting $R(x) = (1+F(x))Q(x),$ it's easy to see that its constant term is simply $1$. Therefore, it would suffice to show that $R(x^2) = R(x),$ since then there would exist no nonconstant term of $R(x)$ with nonzero coefficient, as then considering such a term with minimal degree would lead to a contradiction. So let us show this. Notice that $Q(x^2)$ is simply $\sum_{i = 0} ^{\infty} (-1)^{a_{2i}} x^{2i},$ where we used that $a_i = a_{2i}.$ Therefore, since this is just the even terms, we know that $Q(x^2) = \frac{Q(x) + Q(-x)}{2}.$ Therefore, we know that: $$R(x^2) = (F(x^2) + 1)(Q(x^2)) = (1 + (1-x)F(x) - x)(\frac{Q(x) + Q(-x)}{2}),$$which implies that: $$R(x^2) = (1-x) (1+F(x)) (\frac{Q(x) + Q(-x)}{2}).$$ Hence, as $R(x) = (1+F(x))Q(x),$ we only need to show that $(1-x) \frac{Q(x) + Q(-x)}{2} = Q(x),$ which is equivalent to: $$(1+x)Q(x) = (1-x) Q(-x),$$in other words, we want to show that $(1+x)Q(x)$ is even. But this is immediate upon noticing that $a_{2i+1} = a_{2i} + 1$ for $i \geq 0$, and noticing that $(x^{2i+1} - x^{2i})(1+x) = x^{2i} - x^{2i+2}$, so we're done. $\square$