4
$\begingroup$

I have got a question related to functional equations which is as follow:

Let $N =$ {${1,2,3,...}$}. Determine whether there exists a strictly increasing function $ f : N → N $ with the following properties:

$f(1) = 2$ and $f(f(n)) = f(n)+n$ where $(n ∈ N)$.

I tried applying the method which I apply to every question of such kind.

Put $n=1$ and then $f(f(1)) = f(1)+1\implies f(2)=3$

Put $n=2$ and then $f(f(2)) = f(2)+2\implies f(3)=5$

Now, if I put $n=3$ I will get $f(f(3)) = f(3)+3\implies f(5)=8$.

There are two problems now.

$1.$ I don't see any pattern.

$2.$ If I continue this way. I will miss $n=4,6,7......$

What to do now. Please help, any suggestion is heartily welcome.

Edit: This is IMO1993 Contest Problem 5 (2nd problem on 2nd day).

$\endgroup$
6
  • 1
    $\begingroup$ I see the fibonacci sequence with what is definable through the your method. (1) 1,2,3,5,8,... $\endgroup$ Commented Dec 9, 2016 at 12:43
  • $\begingroup$ Which is always increasing. Am I right ??@KitterCatter $\endgroup$ Commented Dec 9, 2016 at 12:46
  • $\begingroup$ Yeah. Though I think you are right to be uneasy about some of the terms not being well defined. $\endgroup$ Commented Dec 9, 2016 at 12:47
  • $\begingroup$ Well, I agree....:P :P $\endgroup$ Commented Dec 9, 2016 at 12:49
  • $\begingroup$ This question is about the same equation, but for real functions: Find all functions f such that $f(f(x))=f(x)+x$. Found using Approach0. $\endgroup$ Commented Jan 7, 2017 at 15:56

1 Answer 1

6
$\begingroup$

Notice that for $\displaystyle\alpha = \frac{1+\sqrt{5}}{2}$, $\displaystyle\alpha^{2}n=\alpha n+n$ for all $n \in \mathbb N$. We shall show that $\displaystyle f(n)= \lfloor(\alpha n+\frac{1}{2})\rfloor$ satisfies the requirements.


Observe that $f$ is strictly increasing and $f(1)=2$. By the definition of $f$, $|f(n)-\alpha n| \leq \frac{1}{2}$ and $f(f(n))-f(n)-n$ is an integer. On the other hand, $$|f(f(n))-f(n)-n| =|f(f(n)) -f(n)-\alpha^{2}n +\alpha n|$$ $$=|f(f(n))-\alpha f(n) +\alpha f(n) -\alpha^{2}n -f(n) +\alpha n|$$ $$=|(\alpha -1)(f(n)-\alpha n) +(f(f(n))-\alpha f(n))|$$ $$\leq (\alpha -1)|f(n)-\alpha n| + |f(f(n))-\alpha f(n)|$$ $$\leq \frac{1}{2}(\alpha -1) + \frac{1}{2} = \frac{1}{2}\alpha <1$$ which implies that $$f(f(n))-f(n)-n=0.$$ Hope it helps.

$\endgroup$
4
  • $\begingroup$ I didn't get:$|f(f(n))-\alpha f(n) +\alpha f(n) -\alpha^{2}n -f(n) +\alpha n|=|(\alpha -1)(f(n)-\alpha n) +(f(f(n))-\alpha n))|$. I'm missing $-\alpha f(n)$. $\endgroup$
    – Arnaldo
    Commented Dec 9, 2016 at 13:13
  • $\begingroup$ @ArnaldoNascimento, There is a typo, but that does not affect the argument once you correct it. $\endgroup$ Commented Dec 9, 2016 at 13:14
  • $\begingroup$ The occurrence of the golden ratio is natural in view of the recursive formula $$f^{\circ (k+2)}(n) = f^{\circ (k+1)}(n) + f^{\circ k}(n)$$ yet the construction is so simple and elegant. How did you come up with this? (+1) $\endgroup$ Commented Dec 9, 2016 at 13:16
  • 1
    $\begingroup$ @SangchulLee It came naturally! Actually, I got the hint at the comments and after poking about the problem got this solution. $\endgroup$
    – user371838
    Commented Dec 9, 2016 at 13:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .