Find $f(n)$ where $f(2n)= 2f(n)+ 1$

Question

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

Answer 1

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

Answer 2

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

Answer 3

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