How can I prove that two recursion equations are equivalent? 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.

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