How can I prove that two recursion equations are equivalent?

Question

I have two recursion equations that seem to be equivalent. I need a method to show the equivalence relation between them. The equations calculate number of ones in binary representation of the number. The equations are given below:

1) $$ f(0) = 0 $$ $$ f(n) = \begin{Bmatrix} f(n-1)+1 & \text{if n is odd} \\ f(\frac{n}{2}) & \text{if n is even} \end{Bmatrix} $$

2) $$ g(0) = 0$$ $$g(n)=g(n-2^{\lfloor log_2{(n)}\rfloor})+1$$

I thought about using induction, but I have no clue how to use it along with recursive equations. Any help will be appreciated.

Answer 1

The most obvious strategy would be to prove separately that $f(n)$ and $g(n)$ are both equal to the number of ones in the binary representation of $n$. That would be fairly easy to do by long induction on $n$ in each case.

Answer 2

You can do it with induction I believe. The induction hypotheses will have to be chosen cleverly to simplify the expression for $g(n)$. My suggestion would be to do induction steps on an exponential scale. That is, assume that $g(n) = f(n)$ for all $n$ less than or equal to $2^m$. Then, prove that $g(n) = f(n)$ for $n = \left\{2^m+1, \ldots , 2^{m+1}\right\}$.

The reason we want to do this is because, for $n = \left \{ 2^m+1, \ldots, 2^{m+1}-1\right\}$, $\lfloor \log_2(n)\rfloor$ has the constant value $m$. For $n = 2^{m+1}$, $\lfloor \log_2(n)\rfloor = m+1$.