Well, if we look at the first values, we recognize a fibonacci sequence And, one can easily prove (by induction) that, if we denote by $F_p$ the p-th term of this sequence, we have : $f(F_p) = F_p + 1$. So, an idea would be to use $\phi$ (the golden ratio) To be continued

$f(1) = 2 \\ f(2) = f(f(1)) = f(1) + 1 = 3 \\ f(3) = f(f(2)) = f(2) + 2 = 5 \\ f(5) = f(f(3)) = f(3) + 3 = 8$ And in general: $f(F_{n}) = F_{n+1}$, where $F_n$ denotes the nth Fibonacci number. (mathmanman, did you write your subscript incorrectly?) The problem amounts to finding a recursive formula for $F_n$ solely in terms of $F_{n-1}$. I do not know if this is possible, although a formula for $F_n$ in terms of $n$ is known (it doesn't look likely to give a simple solution): $F_n = \displaystyle\frac{1}{\sqrt{5}} \left( \phi^n + \left(1 - \phi \right)^n \right)$. This implies: $f(\displaystyle\frac{1}{\sqrt{5}} \left( \phi^n + \left(1 - \phi \right)^n \right)) = \displaystyle\frac{1}{\sqrt{5}} \left( \phi^{n+1} + \left(1 - \phi \right)^{n+1} \right)$

t0rajir0u wrote: (mathmanman, did you write your subscript incorrectly?) Yeah, sorry Well, in fact, we know that $F_{p+1}$ is the closest integer of $\phi F_p$. Thus, I think the solution to this functional equation would be $f(n) = [\phi n + k]$ where [x] is the integer part of x and k a constant that I have not determined yet :p. To be continued...

Well, if the floor function is allowed, a little bit of algebra and calculation verifies that $\displaystyle\frac{3 - \sqrt{5}}{2} \le k < 3 - \sqrt{5}$ satisfies the criterion for the first few values of $n$, which is sufficient to show that the floor-function solution works for all $n$ since $\displaystyle\frac{F_{n+1}}{F_n} \approx \phi$ becomes more accurate for larger $n$ But it seems like using the floor function is a cheap way to solve the problem... the problem seems like it wants an algebraic function.

t0rajir0u wrote: Well, if the floor function is allowed, a little bit of algebra and calculation verifies that $\displaystyle\frac{3 - \sqrt{5}}{2} \le k < 3 - \sqrt{5}$ satisfies the criterion for the first few values of $n$, which is sufficient to show that the floor-function solution works for all $n$ since $\displaystyle\frac{F_{n+1}}{F_n} \approx \phi$ becomes more accurate for larger $n$ Yeah, that's what I got t0rajir0u wrote: But it seems like using the floor function is a cheap way to solve the problem... the problem seems like it wants an algebraic function. Then, I'm off (and waiting for a more experienced user that'll be able to solve it this way, maybe you? )

I got a recursively defined function f, but I don't like it at all (unfortunately, I think there's no confortable choice here ). Denote $A_p=\{1,2,...,p\}, \ \forall p\in \mathbb {N}.$ Let $f(1)=2$. Suppose we have already defined $f(1),f(2),...,f(n)$ such that $f(1)<f(2)<...<f(n).$ Define $f(n+1)$ as it follows: (i) if $n+1\in f(A_n), \mbox {i.e. }n+1=f(k)$ for some $k \in A_n$, let $f(n+1)=f(k)+k=n+1+k$ (since f is increasing on $A_n$, we cannot have $n+1=f(k)=f(k')$ for $k\neq k'$, so $f(n+1)$ is correctly defined); (ii) if $n+1\notin f(A_n)$, let $f(n+1)=f(n)+1$. I proved that $f(n)<f(n+1)$, so f can be recursively defined on $\mathbb {N}$. Also f is strictly increasing. Now we have to prove that $f(f(n))=f(n)+n, \ \forall n \in \mathbb {N}$. First prove by induction that $f(n)>n, \ \forall n \in \mathbb {N}$, hence $n \in \{1,2,...,f(n)-1\}$ i.e. $n \in A_{f(n)-1}$. It results that $f(n) \in f(A_{f(n)-1})$, so $f(f(n)$ will be calculated as in case (i): $f(f(n))=f(n)+n$, q.e.d.

let n be a natural number.let $F(k)$ be the biggest fibonacci number not biger than n.then $n=F(k)+m$doing the same thing all over again we get a unique way to write n as$n=Fi1+Fi2+...+Fih$.the function $f(F(i1)+F(i2)+...+F(ih))=F(i1+1)+F(i2+2)+...+F(ih+1)$verifies the condition of the problem and it's pretty easy to prove it

bodom wrote: let n be a natural number.let $F(k)$ be the biggest fibonacci number not biger than n.then $n=F(k)+m$doing the same thing all over again we get a unique way to write n as$n=Fi1+Fi2+...+Fih$.the function $f(F(i1)+F(i2)+...+F(ih))=F(i1+1)+F(i2+2)+...+F(ih+1)$verifies the condition of the problem and it's pretty easy to prove it My solution was the same. The representation mentioned here is called base-Fibonacci or Zeckendorf representation of $n$. By the way, in the further proof of why this function is monotonous trivial inequality $F_{n+2}> F_{n}+F_{n-1}+\ldots+F_{1}+F_{0}$ comes in handy.

hmmm... my function was more of a patchwork of Fibonacci-type sequences than anything... I didn't find an explicit closed formula for the function (seeing as the problem didn't ask that) but I however showed a way to construct the function where it meets all the conditions stated in the problem... You start with your base sequence (The one defined for $ 1, 2, 3, 5, ...$) and then, in the spaces which are unoccupied by this sequence, you construct new Fibonacci sequences (of course, you need to prove these new Fibonacci sequences meet all the conditions)

Ignore what I said earlier; floor functions are the key. The sequence is almost certainly (some variant of) a Beatty sequence. In fact I think the closest integer to $ \phi n$ suffices (which agrees with what I said earlier; we can take $ k = \frac{1}{2}$).

Let $q=\frac{\sqrt5+1}{2}$ and $f(n)=[qn+\frac{1}{2}]$. Then $f(1)=2$ $g(n)=qn \to f(n)-g(n)<\frac{1}{2} \to |f(f(n))-f(n)-n|=|(q-1)|g(n)-f(n)+g(f(n))-f(f(n))|\leq (q-1)|g(n)-f(n)|+|g(f(n))-f(f(n))|\leq \frac{1}{2}(q-1)+\frac{1}{2}=\frac{q}{2}<1 \to f(f(n))=f(n)+n$. Exists

Raluca wrote: $f(n)<f(n+1)$ How to prove this assertion? From the condition (ii) of Reluca's post it is clear but I don't see how to prove this from (i).

This one is very easy if you've seen TSTST 2017/6. Anyway, define $f$ in the following way: Let $n=F_{a_1}+\cdots+F_{a_r}$ be the unique Zeckendorf representation of $n$. Then, \[f(n):=F_{a_1+1}+\cdots+F_{a_r+1}.\]This clearly satisfies the FE, so it suffices to show that $f$ is increasing. This is actually just induction on $\max\{a_i\}$, but I'm too lazy to write down the details

I tried to solve it in a similar way as Putnam 1998 function, but got stuck. Can someone help? Denote $a_1=n$, $a_2=f(n)$ and $a_{n+1}=f(a_n)$. Replacing it in the original equation gives $a_{n+2}=a_{n+1}+a_n$. Which is the Fibonacci. But, what to do next?

This is very beautiful problem. I should start with some observation, $f(f(1))=f(1)+1=3=f(2)$. $f(f(2))=f(2)+2=5=f(3)$. Claim(1): $f(f_N)=f_{N+1}$.Here $f_n$ is $n$ th febonacchi number. Proof. we have seen this is true for $N=1,2$ assuming its true for $N=k$ we can conclude, \[f(f_{k+1})=f(f(f_k))=f(f_k)+f_k=f_{k+1}+f_k= f_{k+2}\]. it is very well know that $\lim_{n\to\infty} \frac{f_{n+1}}{f_n} = \phi (\textcolor{blue}{\text{Golden ratio}})$. so we can see that for large $N$ , $f(N)\sim [\phi .N]$. To see why the above observation is true we have to look the given condition we have \[2=f(1)<f(2)<f(3)=5<f(4)<f(5)=8\]now clearly $f(4)$ can be either $6$ or $7$.here $[\phi .4]= 6$ so difference is not large . From here we can guess $f(n)=[\phi.n+k]$ can be a possible solution. where $0<k<1$. \begin{tabular}{lllll} \hline \multicolumn{1}{|l|}{{\color{blue} n}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} \\ \hline \multicolumn{1}{|l|}{{\color{blue} $[\phi.n]$}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{6} \\ \hline \multicolumn{1}{|l|}{{\color{blue} f(n)}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6,7} \\ \hline & & & & \end{tabular}If we put $k=0.4$ on that we must get value of $[\phi.n+0.4]=2=f(1)$ and it will same for $f(3)$ as well. Now look into the following table, \begin{tabular}{lllll} \hline \multicolumn{1}{|l|}{{\color{blue} n}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} \\ \hline \multicolumn{1}{|l|}{{\color{blue} $[\phi.n+0.4]$}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6} \\ \hline \multicolumn{1}{|l|}{{\color{blue} f(n)}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6or7} \\ \hline & & & & \end{tabular} From here I should my final claim which finish this problem. Claim(2): $f(n)=[\phi.n +0.4]$ works. proof. At first of all notice that $[\phi.(n+1)+0.4]\ge [\phi.n+0.4]+[\phi]>[\phi.n +0.4]$. Now assume that $g:\mathbb{N}\to \mathbb{N}$ such that $g(n)=[\phi.n +0.4]$. we have $g(n+1)>g(n)$. Now, \[ g(g(n))=[\phi.g(n) +0.4] =[\phi.([\phi.n +0.4]) +0.4]\] \[ <[\phi.[(\phi.n +0.4) +0.4] =[\phi ^2 .n +0.4+0.4\times \phi]\] \[= [\phi .n +n+0.4+0.4\times \phi] (\text{this is because of} \phi ^2 -\phi -1=0)\] \[\le [\phi .n +0.4]+[n+1+0.4\times \phi ] (\text{I used this fact} [x+y]\le [x]+[y+1])\] \[ = g(n)+n+1 (\text{here } 0.4\times \phi \sim 0.64 ) \] Now it is time to find out lower bound. \[g(g(n)) > [\phi.(\phi.n +0.4-1) +0.4]\] \[=[\phi^2.n +0.4 -0.6\times \phi]\] \[ =[\phi .n +n+0.4-\phi \times 0.6]\] \[\ge [\phi .n +0.4]+[n-\phi \times 0.6]\] \[=g(n)+n-1\] So only possibility is $g(g(n))=g(n)+n$. Again notice that $g(1)=2$. So ,$g(n)=f(n)$ can be a solution to $f$. So, Yes there exists a function as defined in the question.

Very cute problem! From $f(1)=2$ and $f(n)+n=f(f(n))$, one can prove by induction that $f^k(1)=F_{k+2}$, where $F_n$ is the $n$-th term of the Fibonacci's sequence.$ \qquad (\star)$ Now, for each positive integer $n$, by the Zeckedorf's Theorem, $n$ can be written uniquely as $\sum_{i=1}^k F_{a_i}$, wtih $a_{i+1} > a_i+1$. Then, define $f(n)=\sum_{i=1}^k f(F_{a_i}) \quad \forall n \in \mathbb{N}$. From $(\star)$, $$n+f(n)=\sum_{i=1}^k F_{a_i}+\sum_{i=1}^k f(F_{a_i})=\sum_{i=1}^k f(f(F_{a_i})) \underbrace{=}_{\text{uniqueness of $F_{a_i}$}} f(f(n))$$$\implies f(f(n))=f(n)+n$ is satisfied. Furthermore, $f$ is increasing due to our construction and $(\star)$. Hence, we are done. $\blacksquare$

We claim that $f(n)=\left\lfloor\phi n+\frac12\right\rfloor$ fits, where $\phi=\frac{1+\sqrt5}2$. First, we can verify that $f(1)=2$ and that $f$ sends $\mathbb N$ to $\mathbb N$. Since $\phi>1$ we also have that $f$ is increasing. Next, we prove that $f(f(n))=f(n)+n$. Indeed: \begin{align*} f(f(n))-f(n)-n&=\left\lfloor\phi\left\lfloor\phi n+\frac12\right\rfloor+\frac12\right\rfloor-f(n)-n\\ &=\left\lfloor\phi n+n+\frac{\phi+1}2-\phi\left\{\phi n+\frac12\right\}\right\rfloor-f(n)-n\\ &=\left\lfloor\phi n+\frac{\phi+1}2-\phi\left\{\phi n+\frac12\right\}\right\rfloor-\left\lfloor\phi n+\frac12\right\rfloor\\ &\in\left[\left\lfloor\frac\phi2-\phi\left\{\phi n+\frac12\right\}\right\rfloor,\left\lfloor\frac\phi2-\phi\left\{\phi n+\frac12\right\}\right\rfloor+1\right]\\ &\subseteq\left[\left\lfloor-\frac\phi2\right\rfloor,\left\lfloor\frac\phi2\right\rfloor+1\right]\\ &=[-1,1] \end{align*}So since $f(f(n))-f(n)-n$ is an integer, we have $f(f(n))-f(n)-n\in\{-1,0,1\}$. Looking at the equality cases for either side, we see that equality holds only if $\phi n+\frac12$ is an integer. This cannot occur since $\phi$ is irrational. Then the only remaining option is $f(f(n))=f(n)+n$.

Answer is $\boxed{\text{yes}}$. Let $\varphi$ denote the golden ratio , or $\left(\frac{1+\sqrt{5}}{2}\right)$. So $\varphi +1 =\varphi ^2$. We claim that the function $\boxed{f(n)=\left\lfloor \varphi n+\frac{1}{2}\right\rfloor}$ fits. First we will show that the function is strictly increasing. This follows as $\varphi>1$. It suffices to show that $f(f(n))=f(n)+n$. We have \begin{align*} f(f(n))-f(n)-n= & \left\lfloor \varphi \left \lfloor \varphi n+\frac{1}{2}\right \rfloor +\frac{1}{2}-f(n)-n\right\rfloor \\ f(f(n))-f(n)-n= & \left \lfloor \varphi n + n + \frac{\varphi +1}{2}-\varphi\left\{\varphi n+\frac{1}{2}\right\}\right \rfloor -f(n)-n \\ f(f(n))-f(n)-n= & \left \lfloor \varphi n + \frac{\varphi +1}{2}-\varphi\left\{\varphi n+\frac{1}{2}\right\}\right \rfloor - \left\lfloor \varphi n +\frac{1}{2}\right\rfloor \end{align*} First we will maximize $f(f(n))-f(n)-n$. Note that $f(f(n))-f(n)-n\le\left\lfloor \varphi n +\frac{\varphi +1}{2}\right\rfloor - \left\lfloor \varphi n +\frac{1}{2}\right\rfloor \le 1$. Now we will minimize $f(f(n))-f(n)-n$. Note that $f(f(n))-f(n)-n\ge \left\lfloor \varphi n+\frac{1-\varphi}{2}\right\rfloor -\left\lfloor \varphi n+\frac{1}{2}\right\rfloor\ge -1$. Thus, $f(f(n))-f(n)-n\in \{-1,0,1\}$ since it's an integer. Suppose $f(f(n))-f(n)-n=-1$ or $1$. Then $\varphi n +\frac{1}{2}$ is an integer, a contradiction. Thus, $f(f(n))-f(n)-n=0\implies f(f(n))=f(n)+n$. $\blacksquare$

Let $\phi$ be the golden ratio. We claim that the function $\Phi(x)=\lfloor \phi x+.5\rfloor$ works. Note that $\Phi(1)=2$ satisfying (i) and indeed $\Phi$ is strictly increasing. \begin{align*} |x+\Phi(x)-\Phi(\Phi(x))| &=|\phi(\phi x)-\phi \Phi(x)+\Phi(x)-\Phi(\Phi(x))+\Phi(x)-\phi x| \\ &=|(\phi-1)(\phi x-\Phi(x))+\phi \Phi(x)-\Phi(\Phi(x))| \\ &\leq (\phi-1)|\phi x-\Phi(x)| +|\phi\Phi(x)- \Phi(\Phi(x))| \\ &<(\phi-1)/2+.5 =\phi/2 <1\end{align*}Since $x+\Phi(x)-\Phi(\Phi(x))$ is an integer, it has to be zero. So it satisfies (ii).

The problem dies from the following. Lemma: There is a unique number $k$ and sequence $\{c_i\}_{i \le k}$ such that $c_{i+1} > c_i+1$ and \[ n = \sum_{i=1}^k F_{c_i}.\] I contend all $f$ such that $f(n) = \sum f(F_{c_i})$ work. For such $f$, it follows that \[ n + f(n) = \sum [F_{c_i} + f(F_{c_i})] = \sum f(f(F_{c_i})) = f \left(\sum f(F_{c_i})\right) = f\left( f\left( \sum F_{c_i} \right) \right) = f(f(n)). \] Now we show that $f$ is strictly increasing, which would finish. I contend that $f^n(1)=F_{n+2}$ for each nonnegative $n$. This is just induction with the base cases $n=0$, $n=1$ trivially true, and for the inductive step, note that $$f^{n+2}(1) = f^2(f^n(1)) = f^{n}(1)+f^{n+1}(1) = F_{n+2}+F_{n+3} = F_{n+4}.$$Now for $k>0$, let $\{a_{(k, i)}\}_{i \ge 1}$ denote the sequence $c_i$ in the Zeckendorf representation of $k$. Then if $m>n$ for some $m, n$, $\{a_{m, i}\}_{i \ge 1}$ is lexicographically greater than $\{a_{n, i}\}_{i \ge 1}$. Thus by Binet's formula, it follows that $f(m)>f(n)$, and we are done.

Very cute problem. This can be motivated quite well from the known fact that $\frac{F_{n+1}}{F_n} \rightarrow \phi$. We claim that the following function $f$ satisfies all the desired properties. \[f(n) =\lfloor \phi n + 0.4 \rfloor \forall n \in \mathbb{N} \ \ \ \ \ (\phi = \frac{1+\sqrt{5}}{2})\]First, $f(1) = \lfloor \phi + 0.4 \rfloor = \lfloor 2.01\dots \rfloor = 2$. Now, we show that the considered function is strictly increasing. \begin{align*} f(n+1) &= \lfloor \phi (n+1) + 0.4 \rfloor\\ &= \lfloor n\phi + 0.4 + \phi\rfloor\\ & \ge \lfloor n\phi + 0.4\rfloor + \lfloor \phi \rfloor \\ &= f(n) + 1\\ & > f(n) \end{align*}We are now left to confirm the final condition. We do this via some bounding. \begin{align*} f(f(n)) &= \lfloor \phi \lfloor \phi n + 0.4\rfloor + 0.4 \rfloor \\ & < \lfloor \phi(\phi n + 0.4) + 0.4 \rfloor \ \ \ \ \ \ \ \ \ (\lfloor \phi n + 0.4 \rfloor \neq \phi n + 0.4\ \ \ \because \phi \in \mathbb{Q}')\\ & = \lfloor \phi ^2 n + 0.4\phi + 0.4 \rfloor\\ &= \lfloor n(\phi+1) + 0.4\phi + 0.4 \rfloor\\ &= \lfloor n\phi + 0.4 + n + 0.4\phi \rfloor\\ & \le \lfloor n\phi + 0.4\rfloor + \lfloor n + 0.4 \phi \rfloor +1\\ &= f(n) + n +1 \end{align*}Thus, $f(f(n)) \le f(n)+n$. Furthermore, \begin{align*} f(f(n)) &= \lfloor \phi \lfloor \phi n + 0.4\rfloor + 0.4\rfloor\\ & > \lfloor \phi (\phi n + 0.4 -1)+ 0.4\rfloor\ \ \ \ \ \ (\lfloor \phi n + 0.4 \rfloor \neq \phi n + 0.4 - 1\ \ \ \because \phi \in \mathbb{Q}')\\ &= \lfloor \phi ^2 n + (0.4-1)\phi + 0.4 \rfloor\\ &= \lfloor n(\phi +1) - 0.6\phi + 0.4\rfloor\\ &= \lfloor n\phi + 0.4 + n - 0.6 \phi \rfloor\\ & \ge \lfloor n\phi + 0.4\rfloor + \lfloor n- 0.6\phi \rfloor \\ &= f(n) + n -1 \end{align*}Thus, $f(f(n)) \ge f(n) + n$, from which it follows that $f(f(n))=f(n)+n \forall n \in \mathbb{N}$ as desired.