There is an older question here that asks about the function $f(n)$ that gives the number of 1's in the binary representation of $n$. Stated in an equivalent way, this function is:
$f(n) = \begin{cases} \hfill 1 \hfill & \text{ if $n$ is 1} \\ \hfill f(z) \hfill & \text{ if $n$ is 2z} \\ \hfill f(z) + 1 \hfill & \text{ if $n$ is 2z+1} \\ \end{cases}$
My question is about how it can be proved that $f(n) = b_1(n)$, where $b_1(n)$ is the number of 1's in $n$'s binary representation. At first I thought that it could be proved by showing that there existed $2^x-1 $ numbers whose binary representation is of length $x$ and trying to prove that $f(n_1) + f(n_2) + ... + f(n_{2^x-1})$ (where each $n_i$ is the $i$th number of length $x$) are 1's using the pigeonhole principle, but that seems to go nowhere. How is this function derived, and how can it be proved?
Let the binary representation of $n$ be denoted $B(n)$.
When $n=1$, it's clearly true.
When $n=2z$, $B(n) = [B(z)\ 0]$, so $B(n)$ has the same number of ones as $B(z)$ does.
Finally, when $n=2z+1$, $B(n) = [B(z)\ 1]$. So $B(n)$ has an additional one compared to $B(z)$.