I'm trying to show by induction that the sum of the heights of the nodes of a complete binary tree is $N - b(N)$. $N$ is the number of nodes in the tree, and $b(N)$ is the number of 1s in the binary representation of $N$.
I can see that if $N$ is even (ends with 0), then $N + 1$ is odd (ends with 1). Thus, $b(N+1)=b(N)+1$.
How would I go about showing the case when $N$ is odd and $N + 1$ is even? More specifically, how would I express $b(N+1)$ in terms of $b(N)$ in this case?
Perhaps there are more than two cases? Any help would be appreciated.