Find $f(n)$ where $f(2n)= 2f(n)+ 1$ A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the following for all $n$ natural.
$f(1)= 1$
$f(f(n))= n$
$f(2n)= 2f(n)+ 1$
Find $f(n)$
I'm really stuck, new to functions
All I've gotten is :
$f(2(f(f(n)))= 2(f(f(f(n)))+ f(1),$
which isn't very helpful..
 A: You know that $f\left(1\right)=1$. Then
$$
f\left(2\right)=2f\left(1\right)+1=3
$$
$$
f\left(4\right)=2f\left(2\right)+1=7
$$
$$
f\left(8\right)=2f\left(4\right)+1=15
$$
You can then show that
$$
f\left(2^n\right)=2^{n+1}-1
$$
Then what about odd numbers ?
$$
f\left(3\right)=f\left(f\left(2\right)\right)=2
$$
Then $$f\left(6\right)=2f\left(3\right)+1=5$$
$$
f\left(5\right)=f\left(f\left(6\right)\right)=6
$$
I let you continue to find a pattern, knowing how to compute $f\left(n\right)$ for all $n$.
A: Assume* $f$ is uniquely defined and consider the function $g : \mathbb{N} \to \mathbb{N}$ defined by $$g(1) = 1 \\ g(2n) = 2g(n)+1 \\ n\geq 1 \implies g(2n+1) = 2g(n)$$
then it's not hard to see that $g$ satisfies $g(g(n)) = n$ so that $f=g$.
The reason this characterization is nicer is that it can be described simply in terms of the binary expansion of $n$.  That is, to find $g(n)$, write $n$ in binary and flip every bit other than the leading bit.  That is, we keep the most significant $1$, and every less significant bit is flipped, $1$ becomes $0$ and $0$ becomes $1$.
This may be written succinctly as $$f(n) = g(n) = 3\cdot 2^{\lfloor\log_2 n\rfloor}- n - 1$$

*To show $f$ is uniquely determined, it's convenient to define $N(n) = \lfloor\log_2n\rfloor$ and then induct on $N(n)$ to show $f(n)$ is uniquely determined and $N(f(n))=N(n)$.
The base case of $N(n)=0 \iff n=1$ is immediate from $f(1)=1$.
For the inductive step, first assume $n>1$ is even, so that $n=2m$ where $N(m) = N(n)-1$. Then $f(n) = 2f(m)+1$ is uniquely determined and $$N(f(n)) = N(f(2m)) = N(2f(m)+1) = 1+N(f(m)) = 1+N(m) = N(n).$$  Here, we also note that $f(n)$ is odd, where $f(f(n)) = n$ and $N(f(f(n))) = N(n) = N(f(n))$.
This effectively finishes the inductive step, because $N^{-1}[N(n)] = \{k \in \mathbb{N} : N(k) = N(n)\}$ has an equal number of odd numbers and even numbers.  Since $f$ is injective and the above argument can show $k\in N^{-1}[N(n)]$ is even implies $f(k) \in N^{-1}[N(n)]$ is odd, it follows that every odd number in $N^{-1}[N(n)]$ is the image of an even number in $N^{-1}[N(n)]$.
A: WLOG Let $f(m)=g(m)+b$
$$1=f(2n)-2f(n)=g(2n)+b-2(g(n)+b)=g(2n)-2g(n)-b$$
Let $b=-1$  to find $$g(2n)=2g(n)$$
$1=f(1)=g(1)+(-1)\implies g(1)=2$
$$g(2^r)=2g(2^{r-1})=\cdots=2^rg(1)=2^r(2)$$
