Prove that function on naturals defined recursively is idempotent on odd numbers

Question

Consider the function $f$ on natural numbers defined by the following recursion:

• $f(1)=1$
• $f(3)=3$
• $f(2n)=f(n)$
• $f(4n+1)=2f(2n+1)-f(n)$
• $f(4n+3)=3f(2n+1)-2f(n)$

Numerical evidence shows that for odd $k$ we have $f(f(k))=k$, but I have no clue on how to prove it. Any ideas?

Answer 1

Hint: Consider a binary expansion of natural numbers. Take a detailed solution here https://artofproblemsolving.com/community/c6h60400p365112