Let $ b: \mathbb{N} \rightarrow \mathbb{N}$ the function given by
$b(n) = \begin{cases} 0&n=0 \\b\left(\lfloor\frac{n}{2}\rfloor\right) + (n\mod 2) &n>0\end{cases}$
$ \bullet $ How to prove that the number of 1 in the binary representation of n is b(n), for every $n>0$?
$ \bullet $ How to prove that $ b(n) \le\lfloor{log_2 n}\rfloor $, for every $ n > 0 $
Thanks.
HINT: For the first part, suppose that $n=(b_mb_{m-1}\ldots b_0)_{\text{two}}$; then
$$\left\lfloor\frac{n}2\right\rfloor=(b_mb_{m-1}\ldots b_1)_{\text{two}}\;,$$
and clearly
$$b(n)=b\left(\left\lfloor\frac{n}2\right\rfloor\right)+b_0\;.$$
For the second, how many times can you divide an integer $n$ by $2$, throwing away any remainder each time?