utkarshgupta wrote: Let $f:\mathbb{N} \cup \{0\} \to \mathbb{N} \cup \{0\}$ be defined by $f(0)=0$, $$f(2n+1)=2f(n)$$for $n \ge 0$ and $$f(2n)=2f(n)+1$$for $n \ge 1$ If $g(n)=f(f(n))$, prove that $g(n-g(n))=0$ for all $n \ge 0$. Easy induction gives $f(n)=2^{k+1}-n-1$ $\forall n\in[2^k,2^{k+1})$ Any integer $n\ge 0$ may be written in a unique manner in one of the two forms : Either $n=2^u-2^v+t$ where $u>v\ge 0$ and $t<2^{v-1}$ Either $n=2^u-1$ where $u\ge 0$ If $n=2^u-2^v+t$ where $u>v\ge 0$ and $t<2^{v-1}$ : $f(n)=2^v-t-1$ and $g(n)=f(f(n))=t$ So $n-g(n)=2^u-2^v$ and $f(n-g(n))=2^v-1$ and $g(n-g(n))=f(2^v-1)=0$ If $n=2^u-1$ where $u\ge 0$ : $f(n)=0$ and $g(n)=f(f(n))=0$ So $n-g(n)=2^u-1$ and $f(n-g(n))=0$ and $g(n-g(n))=f(0)=0$ Q.E.D.

utkarshgupta wrote: Let $f:\mathbb{N} \cup \{0\} \to \mathbb{N} \cup \{0\}$ be defined by $f(0)=0$, $$f(2n+1)=2f(n)$$for $n \ge 0$ and $$f(2n)=2f(n)+1$$for $n \ge 1$ If $g(n)=f(f(n))$, prove that $g(n-g(n))=0$ for all $n \ge 0$. In fact: the function may be described as the following: Take any non-negative integer $x$, express it in binary system, replace the 1's with 0's an vice versa, and turn it into decimal again. You end up with $f(x)$. This may be easily established by strong induction. By this description, $g(x)$ turns out to the number you get when you delete the leftmost block of 1's in the binary representation of $x$. Subtracting this from $n$ leaves only that block of 1s, followed by zeroes. If you again apply $g$ on it, even that block of 1s gets removed, so we get $0$, as desired.