How find this function $f(2^m)=?$

Question

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$

and Find $f(2^m),m>2,m\in N$

My try: let $n=3$ ,then we have $$f(3)=f(f(2))+f(3-f(2))=f(1)+f(3-1)=f(1)+f(2)=2$$ $$f(4)=f(f(3))+f(4-f(3))=f(2)+f(2)=4$$ $$f(5)=f(f(4))+f(5-f(4))=f(4)+f(1)=5$$ $$f(6)=f(f(5))+f(6-f(5))=f(5)+f(1)=6$$ $$f(7)=f(f(6))+f(7-f(6))=f(6)+f(1)=7$$ $$f(8)=f(f(7))+f(8-f(7))=f(7)+f(1)=8$$ so I guess $$f(n)=n,n\ge 4$$

But my question: How to prove that there exists unique $f$ which fulfills these two conditions?

Thank you

Answer 1

First of all, $f(4)=f(2)+f(2)=2$.

About uniqueness it is sufficient to show that $f(n)$ is positive and $f(n)<n$. This means that $f$ can be uniquely determined using the recursive equation. It is possible by induction.

Base case: $n=3, f(3)=2<3, f(3)>0$

Inductive step:

$f(n-1)<n-1 \to f(f(n-1))<f(n-1) \\ n-f(n-1)<n \to f(n-f(n-1))<n-f(n-1)$

Adding both sides of the inequalities we get $f(n)<n,f(n)>0$.

I guess $f(2^m)=2^{m-1},m \ge 1$