Proof of function that gives 1's in binary representation

Question

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?

Sorry, that was unclear. I changed it in the original question. I meant it to mean the $k$th number of length $x$. — Wyatt Gregory, Sep 25 '15 at 18:37
Huh, I would have figured you meant the digit of $n$ at binary index $k$ and then you would use $1,2,...,x$ for indices... — abiessu, Sep 25 '15 at 18:39

score 2 · Accepted Answer · answered Sep 25 '15 at 18:44

2

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)$.

answered Sep 25 '15 at 18:44

Adina Goldberg

454

1

You may also want to verify that these three cases cover all natural numbers, and recursively bottom out at n=1. – Adina Goldberg Sep 25 '15 at 18:46

Proof of function that gives 1's in binary representation

1 Answers1