# IMO problem from 1993 on functional equations

Let N={1,2,3,…}. Determine if there exists a strictly increasing function $$f:N→N$$ such that

1. $$f(1)=2$$

2. $$f(f(n))=f(n)+n$$ for all n."

Here is the solution I came up with

We can see $$f(1)=2$$

$$f(2)=3$$

$$f(3)=5$$

Basically if $$a_n$$ is the $$(n+2)^{th}$$ term in the Fibonacci sequence starting from 1,1,2,3,5..

then I claim

$$f(a_n)=a_{n+1}$$

This can easily be proved by induction as follows

Assume $$f(a_n)=a_{n+1}$$

Then $$f(a_{n+1})=f(a_{n})+a_n=a_{n+2}$$

Now clearly $$a_{n+1}-a_n

So all numbers between $$a_n$$ and $$a_{n+1}$$ can be assigned any arbitrary value between $$a_{n+2}$$ and $$a_{n+1}$$ in increasing order and hence many such functions may exist

I wanted to know if my solution is correct because it looks rather simple and this is an IMO problem

• In the step "so all numbers.. can be assigned arbitrary value..." how do you make sure the assignment satisfies condition 2? Commented Sep 28, 2023 at 8:07
• Remember that $f(f(n))=f(n)+n$ must hold true for all numbers, so $f(f(4))=f(4)+4$, for example. So you can't just assign arbitrary values. Commented Sep 28, 2023 at 8:15
• @MichalAdamaszek thank you now I see my mistake However can I still prove that there will be values that satisfy condition 2 so that such a function may exist without finding such a function Commented Sep 28, 2023 at 8:57
• I don't have any hint. You were asking "is it possible to prove that an object exists without constructing it explicitly". The answer is in general yes. I don't have any clue how you would do it in this specific example. Have a look around, this functional equation was answered a few times on this page. Commented Sep 28, 2023 at 9:02
• Note that if you follow your suggested strategy greedily, then you will assign $f(4)=6$ as first available and then necessarily $f(6)=f(4)+4=10$; after this, $f(7)=9$ as first available and then necessarily $f(9)=9+7=16$, $f(16)=16+9=25$, $f(25)=25+16=41$; after this, $f(11)=14$ as first available, and then $f(14)=14+11=25$, $f(25)=25+14=39$ -- oops! Commented Sep 28, 2023 at 9:25

In the step "assigning arbitrary values" the condition $$f(f(n))=f(n)+n$$ may not hold.