$n\to3$, $\Rightarrow$: $f(3)=f(1)+f(2)=2$, $n\to4$, $\Rightarrow$: $f(4)=f(2)+f(2)=2$, $n\to5$, $\Rightarrow$: $f(5)=f(2)+f(3)=3$, $n\to6$, $\Rightarrow$: $f(6)=f(3)+f(3)=4$, $n\to7$, $\Rightarrow$: $f(7)=f(4)+f(3)=4$, $n\to8$, $\Rightarrow$: $f(8)=f(4)+f(4)=4$.... Then by induction assume that for all $2\le{k}\le{m}$ $f(2^m)=2f(2^{m-1}),f(2^{m+1}-1)=f(2^m)+f(2^m-1)$ which is equvivalent to: $2f(2^m)=f(2^{m+1}-1)=2^m$ $n\to{m+1}$, $\Rightarrow$: $f(2^{m+1})=f(2^m)+f(2^m-1)=2^m$.So , for all $m\ge2$,$f(2^m)=2^{m-1}$. Please,point out any flaw!

My procedure is exactly the same, just got stuck in induction. Could you write that step more clearly, IMI-Mathboy?

International competition SRMC 2005 P-4

http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html

Hint of my solution: After showing there exist only a function, First prove $f(n) \ge f(n+1) \ge f(n)+1$ with induction And use induction to prove $f(2^m)=2^{m-1}$ Also Induct $f(2^m-m)=2^{m-1}-1,f(2^m-m+1)=2^{m-1},f(2^m+1)=2^{m-1}+1$ Therefore there exist $2^{m-2}$ n in $[2^{m-1}+1,2^m]$ such that f(n)>f(n-1) Let t be the smallest number such that $f(t)=2^m$ The main part is to count the number of x in $[2^m+1,t]$, f(f(x-1))>f(f(x-2)) or f(x-f(x-1))>f(x-1-f(x-2)) Then get $ t=2{m+1}-m $

A solution (from a friend): Assuming $f$ exists (which is not hard to show, by adding the condition $f(n)\le n$ and then inducting), we must have $f(n)\le n$ for all $n$ (otherwise $f(n+1)$ is not properly defined). So we have that $1\le f(n),n+1-f(n)\le n$. It is straightforward to show that $f(n)\ge \frac{n}{2}$ via induction, as well as $f(n+1)=f(n)+1 \text{ or } f(n)$ for all $n$. We now prove $f(2^m)=2^{m-1}$. It is easy to verify that this is true for $m=1,2$. Now assuming $m=1,...,k$ is true, we want to show that $f(2^{k+1})=2^k$. Because $f$ increases at most 1 step at a time, and that $f(2^{k+1}-1)\ge 2^k$, there exists $a$ such that $f(a)=2^k$ and $a\le 2^{k+1}-1$. Hence $f(a)\ge a+1-f(a)$. Since $f$ is increasing, \[2^k\le f(a) \le f(a+1)=f(f(a))+f(a+1-f(a))\le 2f(f(a))=2^k\] Thus $f(a+1)=2^k$. Repeating this argument, we have that $f(2^{k+1})=2^k$. EDIT: Small typo somewhere EDIT^2: Another typo. Thanks to perfectstrong.

DVDthe1st wrote: A solution (from a friend): Hence $f(a)\le a+1-f(a)$. EDIT: Small typo somewhere Could you explain that clearlier? I don't think it's right!

Let me try this. Firstly we will prove the following: for any $n\ge 2$ we have \[f(n)-f(n-1)\in\{0,1\}\text{ and }\frac{n}{2}\le f(n)\le n.\] This is true for $n=2.$ Assume that it's true forall $2\le n<N,$ we will show that this is also true for $N.$ Actually, we have \[\begin{aligned}f(N)-f(N-1)=f(f(N-1))&-f(f(N-2))\\&+f(N-f(N-1))-f(N-1-f(N-2)).\end{aligned}\] Since $f(N-1)\le N-1<N$ and $f(N-2)\le N-2<N-1$ and $f(N-1)-f(N-2)\in\{0,1\}$ by inductive hypothesis, we consider two cases: 1. If $f(N-1)=f(N-2)$ then $f(f(N-1))=f(f(N-2))$ and \[\begin{aligned}f(N-f(N-1))&-f(N-1-f(N-2))\\&=f(N-f(N-1))-f(N-f(N-1)-1)\in\{0,1\},\end{aligned}\] so $f(N)-f(N-1)\in\{0,1\}.$ 2. If $f(N-1)=f(N-2)+1$ then $f(N-f(N-1))=f(N-1-f(N-2))$ and $f(f(N-1))-f(f(N-2))=f(f(N-2)+1)-f(f(N-2))\in\{0,1\},$ so $f(N)-f(N-1)\in\{0,1\}.$ Therefore, $f(N)-f(N-1)\in\{0,1\}$ and since $f(N-1)\le N-1,$ $f(N)\le N.$ Moreover, \[f(N)=f(f(N-1))+f(N-f(N-1))\ge\frac{f(N-1)}{2}+\frac{N-f(N-1)}{2}=\frac{N}{2},\] by the inductive hypothesis. Hence proved, and it follows that the existence of the function is unique. Secondly we claim $f(2^m)=2^{m-1}$ forall $m\in\mathbb{N}$ by induction. Assume that the claim is true forall $1\le m<M,$ we prove that $f(2^M)=2^{M-1}.$ The key is the following: forall $2^{M-1}\le n<2^{M}$ we have $f(n)\le 2^{M-1}.$ We proceed again by induction. If $n=2^{M-1}$ everything is clear. Assume now that it is true for $n,$ we prove it is also true for $n+1<2^M.$ Since \[f(n)\le 2^{M-1},\; n+1-f(n)\le n+1-\frac{n}{2}=\frac{n+2}{2}\le\frac{2^M}{2}=2^{M-1},\] we have $f(n+1)\le f(2^{M-1})+f(2^{M-1})=2^{M-1}.$ Now $f(2^M-1)\le 2^{M-1},$ and $f(2^M-1)\ge \frac{2^M-1}{2}$ follows that $f(2^M-1)\ge 2^{M-1},$ so $f(2^M-1)=2^{M-1}.$ Thus \[f(2^M)=f(f(2^M-1))+f(2^M-f(2^M-1))=2^{M-1}.\]

hi @IMI-Mathboy; Please, can you write that step more clearly? I don't understand, i just think you have some mistakes.

Is there a way to get all $ f(n) $ ? Maybe too hard?

Claim: $0\le f(n+1)-f(n)\le 1$ Proof: We will proceed with strong induction. As the base case is trivial, suppose $f(k+1)-f(k)$ for all $k<n$. Then, if $f(n)-f(n-1)=0$, $f(n+1)-f(n)=f(n+1-f(n))-f(n-f(n))$, which is between $0$ and $1$ by induction. Similarly, if $f(n)-f(n-1)=1$, we get $f(n+1)-f(n)=f(f(n-1)+1)-f(f(n-1))$, which finishes by inductive hypothesis again. If we denote $a_i=f(i-1)$, $b_i=i-f(i-1)$, our proof above shows that if $f(i+1)=f(i)$, $(a_{i+1},b_{i+1})=(a_i,b_i+1)$, and if $f(i+1)=f(i)+1$, $(a_{i+1},b_{i+1})=(a_i+1,b_i)$. Now, we use induction to prove that $f(k)=2^{m}$ for $2^{m+1}-m\le k\le 2^{m+1}$. The base case is trivial, so suppose our claim is true for $m$. Consider the first $x_0$ such that $b_{x_0}=2^m-m+1$. As $b_{2^m+1}=2^{m-1}+1$, $f(x)$ is held constant $2^{m-1}-m$ times as $x$ goes from $2^m+1$ to $x_0$. $f(b_x)$ goes from $2^{m-2}+1$ to $2^{m-1}$, as $b_x$ ranges between $2^{m-1}+1$ and $2^m-m+1$, its value has been held constant $2^{m-1}-m-2^{m-2}+1=2^{m-2}-m+1$ times, so $f(a_x)$ has been held constant $2^{m-1}-1$ of the times $a_x$ has been incremented. From this, it is not hard to see that we must have $a_{x_0}=2^m-1$. Now, we just use inductive hypothesis. $a_{x_0+1}=a_{x_0}+1$, and then $b_{x_0}$ is incremented $m-1$ times afterwards, until $b_{x_0}$ reaches $2^m$, since $f(x)$ is constant over all $x\in [2^m-m+1,2^m]$. Throughout this entire process, we have that $f(x)=f(a_x)+f(b_x)=2^m$, since they both lie in the aforementioned interval, and $x=a_x+b_x$ ranges over $2^{m+1}-m$ to $2^{m+1}$. Thus, the inductive step is complete.

It's just A004001 on OEIS.

Proposition. (i) $f(n)\leq n\leq 2f(n)$ (ii) $f(n)-f(n-1)=0\text{ or }1$ The proof is just simple induction. Now (i) implies that if $f(1),...,f(n-1)$ are given then $f(f(n-1))$ and $f(n-f(n-1))$ are already defined and hence we can pin down $f(n)$. This shows that $f$ is unique. Now we show that $f(2^m)=2^{m-1}$. In addition we will show that $f(2^m-m)=2^{m-1}-1$ and $f(2^m-m+1)=2^{m-1}$. The base cases is obvious by checking. We now consider the case $m$ assume that all smaller cases hold. Suppose $x=f(2^m-m)$. Notice that $$x+1=f(2^m-m)+1\geq f(2^m-m+1)=f(x)+f(2^m-m-x)\geq\frac{x}{2}+f(2^m-m-x)$$hence$$\frac{x}{2}\geq f(2^m-m-x)-1$$If $x\leq 2^{m-1}-3$, then right hand side is at least $f(2^{m-1}+2)-1=2^{m-2}-1>\frac{x}{2}$, contradiction. Hence $x\geq 2^{m-1}-2$ Meanwhile, let $n$ be the smallest integer such that $f(n)=2^{m-1}+1$, then $f(n-1)=2^{m-1}$. Therefore, $$f(n)=f(2^{m-1})+f(n-2^{m-1})=2^{m-2}+f(n-2^{m-1})$$Hence $f(n-2^{m-1})\geq 2^{m-2}+1> f(2^{m-1})$ which implies $$n\geq 2^m+1\hspace{20pt}(1)$$In particular, $x\leq 2^{m-1}$. therefore, $$f(2^m-m+1)=f(x)+f(2^m-m-x)=2^{m-2}+2^{m-2}=2^{m-1}\hspace{20pt}(2)$$Let $n_1$ be the smallest integer such that $f(n_1)=2^{m-1}$ then similarly we have $$f(n_1)=f(2^{m-1}-1)+f(n_1-2^{m-1})=2^{m-2}+f(n_1-2^{m-1})$$Hence $n_1\geq 2^m-m+1$. This implies $x=2^{m-1}-1$. Finally, (1) implies $$f(2^m)\leq 2^{m-1}$$and (2) implies $$f(2^m)\geq f(2^m-m+1)=2^{m-1}$$as desired.