This is $f(f(n))=2^{n-1}+c$ where $c$ is a non negative integer And obviously infinitely many such functions exist (since the set of positive integers which are not a power of two is infinite)

^ Can you provide an example of one such function?

e_plus_pi wrote: ^ Can you provide an example of one such function? One family of solutions (with $c=1$) : Let $g(n)=2^{n-1}+1$ from $\mathbb N\to\mathbb N$ Let $A=\mathbb N\setminus g(\mathbb N)$ $A$ is an infinite set (it contains at least all even integers $\ge 4$) and so can be split in two equinumerous subsets $A_1,A_2$ Let $h(x)$ any bijection from $A_1\to A_2$ Any positive integer $>1$ may be written in a unique manner as $x=g^{[n(x)]}(a(x))$ where $n(x)$ is a function from $\mathbb N\to\mathbb Z_{\ge 0}$ and $a(x)$ is a function from $\mathbb N\to A$ Define then $f(x)$ as : $f'(1)=1$ $forall x>1$ : If $a(x)\in A_1$ : $f(x)=f(g^{[n(x)]}(a(x)))=g^{[n(x)]}(h(a(x)))$ If $a(x)\in A_2$ : $f(x)=f(g^{[n(x)]}(a(x)))=g^{[n(x)+1]}(h^{[-1]}(a(x)))$

Other solution for this?

+)$f(2^n)=2^n$ with $ n \in \mathbb{N}$ +)$f(n)=2^{n-1}$ with $n$ isn't power of $2$.

karitoshi wrote: +)$f(2^n)=2^n$ with $ n \in \mathbb{N}$ +)$f(n)=2^{n-1}$ with $n$ isn't power of $2$. Unfortunately wrong. Choose for example $n=4$ $f(f(n+1))=f(f(5))=f(2^4)=2^4=16$ $f(f(n))+2^{n-1}=f(f(4))+2^3=4+8=12$

Let $g(x)=f(f(x))$ so then our problem is $g(x+1)=g(x)+2^{n-1}$ for example $g(1)=t$ . then $g(2)=t+1$ . then $g(3)=t+1+2=t+3$ . Now we are going to use induction . we like to show $g(n) = t + 2^{n-1}-1$. 1 . Base : $g(1) = t+1-1 = t $ that is true ! . we imagine $g(n-1) = t + 2^{n-2}-1$. then we want prove $g(n) = t + 2^{n-1}-1$. we know $g(n)=g(n-1)+2^{n-1}=t + 2^{n-2}-1+2^{n-1} = t+2^{n-2}(2-1) -1 = g(n) = t + 2^{n-1}-1$

what did you do after that